Binary Search

tahmedge

Suppose you are given an array of numbers and you need to find whether the number X is in the array. The straight forward approach to do that would be to run a loop and compare each number in the array with X. This is what the pseudo code would look like:

function findNumber(A, x)
  for i = 0 to length of array A
    if A[i] == x
      return true
  return false

For example, let's assume you are given this array:

[7, 14, 17, 21, 35, 60, 92, 121, 155]

And, you were looking for the number 92. The loop would start checking each of the number in the array against 92 and would find after iterating through the array 7 times.

The worst case time complexity of this approach would be O(n).

However, whenever the array itself is in sorted order (like in this case where the numbers are increasing in value from left to right of the array), you can perform something that is much more efficient: binary search.

The prerequisite of binary search is that the array should be sorted.

How Does Binary Search Work?

Let's use the same array as an example here:

[7, 14, 17, 21, 35, 60, 92, 121, 155]

The numbers are sorted in increasing order, so it satisfies the prerequisite of binary search. Here, the length of the array (N) is 9. The value of the element in the middle is 35. The starting index is 0, the ending index is 8, and the middle index is 4 [(0+8) / 2].

To look for 92 in this array, we need to first compare the middle value with 92. Since 92 is larger than 35, it can be said that all of the values in the array to the left of 35 will definitely be smaller than 92. And, if 92 were to exist in the array, it would exist to the right of 35 (where the values larger than 35 are).

7, 14, 17, 21, 35, [60, 92, 121, 155]

We will now move our starting index immediately to the right of the middle index:

$\\text{Start} = \\text{Mid} + 1 = 4 + 1 = 5$

Our middle index will now change as well:

$\text{Mid} = \lfloor{(\text{Start} + \text{End}) / 2}\rfloor = \lfloor{(5+8) / 2}\rfloor = 6$

Now that we have a new middle value, let's compare it with the number we are looking for. At index 6, we have 92 and turns out that is the number we are looking for. So, we have found 92 in our array.

In this approach we had to perform just two comparisons which is much more efficient than the approach we saw at the beginning of this tutorial.

Another Example

Let's look at another example: We have the same array, but now we are looking for the number 17.

We begin with the starting index 0, ending index 8 and middle index 4. We compare the middle value (35) with the number we are looking for (17). The number we are looking for is smaller than the middle value. Therefore we can say that the number 17 can exist only on the left half of the array.

[7, 14, 17, 21], 35, 60, 92, 121, 155

To narrow down our search in the next step, we will move the ending index to the left of the middle index:

$\text{End} = \text{Mid} - 1 = 4 - 1 = 3$

We will then recalculate our middle index:

$\text{Mid} = \lfloor{(\text{Start} + \text{End}) / 2}\rfloor = \lfloor{(0+3) / 2}\rfloor = 1$

Now our middle index is 1 and middle value is 14. Comparing the value with 17, we see that the middle value is smaller than the number we are looking for. Therefore, the number we are looking for can only appear on the right of the middle index.

7, 14, [17, 21], 35, 60, 92, 121, 155

So, we shift our starting index to the right of the middle index:

$\text{Start} = \text{Mid} + 1 = 1 + 1 = 2$

And, we recalculate our middle index:

$\text{Mid} = \lfloor{(\text{Start} + \text{End}) / 2}\rfloor = \lfloor{(2+3) / 2}\rfloor = 2$

Now our middle index is 2 and middle value is 17. And, 17 is the number we were looking for.

What If The Number Doesn't Exist?

Let's use the same array, but this time we will look for the number 51.

Initially our starting index is 0, ending index is 8, and middle index is 4. The middle value is 35, which is smaller than the 51 (the number we are looking for). Therefore we shift our search to the right half of the array:

7, 14, 17, 21, 35, [60, 92, 121, 155]

We recalculate our starting and middle indices. Following the math outlined above, the new starting and middle indices would be 5 and 6 respectively. The middle value is now 92.

7, 14, 17, 21, 35, [60], 92, 121, 155

Since 51 is smaller than 92, we shift our search to the left. We recalculate our ending and middle indices. The new values of the ending and middle indices are now 5 and 5 respectively. The number 60 is larger than the number we are looking for and so we try to shift to the left one more time.

The new ending index is now 4. Since the ending index has moved to the left of the starting index (i.e. the starting index is greater than the ending index) we can stop our search.

In the situation where the ending index is less than the starting index, it can be concluded that the number we are looking for doesn't exist in the array.

The Algorithm

Here is what the pseudo code of binary search would look like:

function binarySearch(A, x)
  let start = 0
  let end = length of array A
  while start < end
    let mid = (start + end) / 2 # Integer division
    if A[mid] == x
      return true
    else if x > A[mid]
      start = mid + 1
    else if x < A[mid]
      end = mid - 1
  return false

Since at every step we are reducing the search space by half, the worst case time complexity of binary search is $O(log(N))$.