# Why does binary search work this way?

• Arnoldjavs3
In summary, the given code aims to search for a searched value in an array by dividing the array into smaller subarrays and checking if the middle element matches the searched value. If it does not, the algorithm reduces the remaining range to be searched by adjusting the beginning and end values. This is necessary because integer division may result in an incorrect middle value, thus requiring the -1 and +1 adjustments to ensure that all elements in the array are checked. Without these adjustments, the algorithm may still work, but with varying degrees of accuracy.
Arnoldjavs3

## Homework Statement

Java:
public class BinarySearch {
public static boolean search(int[] array, int searchedValue) {
int beginning = 0;
int end = array.length - 1;

while (beginning <= end) {
int middle = (beginning + end) / 2;
if (array[middle] == searchedValue) {
return true;
}
else if (array[middle] > searchedValue) {
end = middle - 1;
}
else if (array[middle] < searchedValue) {
beginning = middle + 1;
}

}
return false;
}
}
/*
middle = 3
array[3] > -3
end = 3;
middle = 0 + 3 /2 = 1.5 so 1
array[1]>-3
end = 1
middle = 0 + 1 /2 = 0
array[0] == -3
return true
*/

## The Attempt at a Solution

The following code is meant to search if an array has a searched value(from the user). My question is why do we need to do this:
end = middle - 1
and
beginning = middle + 1

I noticed that when I input some values without the + and - 1 in the algorithm that it still works, to a varying degree. Why is this?

Arnoldjavs3 said:
I noticed that when I input some values without the + and - 1 in the algorithm that it still works, to a varying degree. Why is this?
Think about what one iteration through the loop will accomplish. Written down in words:

Each iteration will either: 1) Find the searched-for value or 2) Reduce the remaining range to be searched.

Can you think of a way that 2) could fail without the -1 and +1? Hint: integer division.

## 1. Why is binary search more efficient than linear search?

Binary search is more efficient because it cuts the search space in half with each iteration, while linear search checks each element one by one. This makes the search time logarithmic, meaning it grows at a slower rate compared to linear search.

## 2. How does the concept of "divide and conquer" apply to binary search?

The "divide and conquer" approach refers to splitting a problem into smaller subproblems and solving them individually. In binary search, the array is divided into two halves at each iteration, narrowing down the search space until the target element is found.

## 3. Why does binary search only work on sorted arrays?

Binary search relies on comparing the target element with the middle element of the array. If the array is not sorted, the middle element may not accurately represent the elements in the array, leading to incorrect comparisons and a faulty search process.

## 4. Can binary search be used on other data structures besides arrays?

While binary search is commonly used on arrays, it can also be applied to other data structures such as trees and linked lists. However, the data structure must be sorted for binary search to work effectively.

## 5. How does the time complexity of binary search compare to other search algorithms?

Binary search has a time complexity of O(log n), which is more efficient than linear search (O(n)) but less efficient than other algorithms like hash tables (O(1)). However, for large datasets, the difference in time complexity can make a significant impact on performance.

• Engineering and Comp Sci Homework Help
Replies
18
Views
2K
• Engineering and Comp Sci Homework Help
Replies
4
Views
1K
• Engineering and Comp Sci Homework Help
Replies
3
Views
1K
• Engineering and Comp Sci Homework Help
Replies
15
Views
2K
• Engineering and Comp Sci Homework Help
Replies
5
Views
1K
• Engineering and Comp Sci Homework Help
Replies
3
Views
1K
• Engineering and Comp Sci Homework Help
Replies
17
Views
5K
• Engineering and Comp Sci Homework Help
Replies
7
Views
1K
• Engineering and Comp Sci Homework Help
Replies
2
Views
2K
• Engineering and Comp Sci Homework Help
Replies
5
Views
1K