Binary Search – Arrays

What is Binary Search in Data Structures?

As we know to search for a particular given value in an array, we need to traverse the whole array. This method has a high time complexity of O(n). So, we also have an efficient method for this which reduces the time complexity for searching a particular element to O(logn). This searching technique is called binary search.

Binary search can only be implemented when the array is sorted. When it is unsorted, we need to sort it first using any sorting technique.

In this technique, an element is always searched in the middle of the array. If it is present in the middle, then the middle index is returned as the index containing that value. If not, then two cases arise –

• The middle element is greater than the value we are searching for – In this case, the value we are searching for must be on the left. Because the array is sorted. So, we will now search in the left half from the middle.
• The middle element is smaller than the value we are searching for – In this case, the value we are searching for must be in the right half. So, we will now search in the right half from the middle.

Also check: Bellman ford algorithm in data structure

What if the element is not present in the array?

When we searched in even the smallest left and right halves i.e., of size 1, the element is not found. It means the element is not present in the array.

We will understand it better with a diagrammatic representation –

For example, we are searching for the value 5 in our array which contains the values 4,5,6,7, and 8.

So, we will set a pointer low, which will point to the starting index of 0.

After that, we will set a high pointer which will point to the last index.

And finally, we will set a middle pointer which will point to the middle value of the array which is given by (low+high)/2.

Now, we will compare the middle value to the value we are searching for. In this case, we are searching for the value 5 and the middle element is 6. As the middle element is greater than the value we are searching for and the array is sorted, it is clear that the value must be present towards the left of the array because all the values less than the middle are towards the left.

So, we will move the high pointer to mid-1.

Now, the high is pointing to index 1. And the middle is (0+1)/2 i.e., 0. We will now compare 5 to the value at the middle index. As the value at the middle index is 4, and the value we are searching for is 5, which is greater than the middle, that means the value must be towards the right of the middle.

So, we will shift our low to middle+1

Now, the middle element is calculated as (1+1)/2 i.e., 1 and this element matches the value we are searching for. So, that means the element we are searching for is found at this location.

From diagrammatic representations, it must be clear how the binary search works for an array, now we will understand the code for this –

#include <iostream>
using namespace std;
int binarySearch(int array[], int x, int low, int high) {
  while (low <= high) {
    int mid = low + (high - low) / 2;
    if (array[mid] == x)
      return mid;
    if (array[mid] < x)
      low = mid + 1;
    else
      high = mid - 1;
  }
  return -1;
} 
int main(void) {
  int array[] = {1,2,3,4,5,6,8,15};
  int x = 8;
  int n = sizeof(array) / sizeof(array[0]);
  int result = binarySearch(array, x, 0, n - 1);
  if (result == -1)
    printf("Not found");
  else
    printf("Element is found at index %d", result);
}

Output –

Element is found at index 6.

So, in this article, we learned about one of the efficient searching algorithms i.e., Binary Search.

Apart from searching, binary search can also be used to  –

• Given A a sorted array find out how many times does x occur in A.
• Given a real number x, find out its cubic root.
• Given A a sorted array with distinct numbers, find out i such that A[i] == i.
• Given the +,-,*,/, sqrt operations and a real number x find an algorithm to get log_2_x.
• Given an array of distinct numbers A such that A[0] > A[1] and A[n-1] > A[n-2] find out a local minimum (find out an i such that A[i-1] > A[i] < A[i + 1]).
• Let A be a sorted array with distinct elements. A is rotated k positions to the right (k is unknown). Find out k.
• Let A be a sorted array with distinct elements. A is rotated k positions to the right (k is unknown). Find out if A contains a number x.
• Given two sorted arrays of length n and m, find out the kth element of their sorted union.
• Given A, an array comprised of an increasing sequence of numbers followed immediately by a decreasing one. Determine if a given number x is in the array.