Binary Search

Till now, we have studied two sorting algorithms which implemented the Divide and Conquer technique. Binary search is a searching algorithm which uses the Divide and Conquer technique to perform search on a sorted data.

Normally, we iterate over an array to find if an element is present in an array or not. But think about a case when the data which we are provided is a sorted one, then performing a normal search will do the work but shouldn't we extract something useful from the fact that our data is already sorted?

So, let's have a look at the working of the binary search and find out how to perform an optimized search on a sorted data.

Working of Binary Search

---

In binary search, we directly hit the middle element and then compare it with the element to be found.

If the element to be found is equal to the middle element, then we have already found the element, otherwise, if it is smaller, then we know it is going to lie on the left side of it, else, on the right.

Let's take the case when the element to be found is smaller than the middle element, then we will repeat the same procedure on the left subarray by hitting the middle element of the left subarray.

So, this is how binary search works. But before discussing the code of the binary search let's first compare binary search with the traditional search.

Binary Search V/S Traditional Search

---

In traditional search, we iterate over the array and in the worst case, it might be possible that we end up iterating over the entire array and thus, traditional search is a $O\left(n\right)$ algorithm.

Let's talk about the binary search. In binary search, without doing any analysis, we can see that the array is divided into half its initial size each time. So even in the worst case, it would end up searching only ${\log }_{2}n$ elements.

Thus, binary search is a $O\left(\lg n\right)$ algorithm. We are also going to mathematically see this running time later in this chapter.

Coding Binary Search

Our function is going to take an array, starting index, ending index and the element to be searched (x). So, we can declare the function for the binary search as BINARY-SEARCH(A, start, end, x).

We start by hitting the middle element, so let's start by calculating the middle element first i.e., middle = floor((start+end)/2).

Now, we have to compare this element with the element to be searched and if the element to be searched is the middle element, then we end up the function by returning its index i.e.,

if A[middle]==x
  return middle

If the element is smaller than the middle element, then we will repeat the binary search in the left subarray.

if A[middle]>x
  return BINARY-SEARCH(A, start, middle-1)

Similarly, we will repeat with the right subarray if the element to be found is greater than the middle element.

if A[middle]<x
  return BINARY-SEARCH(A, middle+1, end)

Thus, the entire code for the binary search can be written as:

BINARY-SEARCH(A, start, end, x)
  if start <= end
    middle = floor((start+end)/2)
    if A[middle]==x
      return middle

    if A[middle]>x
      return BINARY-SEARCH(A, start, middle-1, x)

    if A[middle]<x
      return BINARY-SEARCH(A, middle+1, end, x)

  return FALSE // in case, element is not in the array