Binary Search

 Problem: Given a sorted array arr[] of n elements, write a function to search a given element x in arr[] and return the index of x in the array. Consider array is 0 base index.

Interval Search: These algorithms are specifically designed for searching in sorted data-structures. These type of searching algorithms are much more efficient than Linear Search as they repeatedly target the center of the search structure and divide the search space in half. For Example: Binary Search.

Binary Search to find the element “23” in a given list of numbers

Examples: 

Input: arr[] = {10, 20, 30, 50, 60, 80, 110, 130, 140, 170}, x = 110
Output: 6
Explanation: Element x is present at index 6. 

Input: arr[] = {10, 20, 30, 40, 60, 110, 120, 130, 170}, x = 175
Output: -1
Explanation: Element x is not present in arr[].

Linear Search Approach: A simple approach is to do a linear search. The time complexity of the Linear search is O(n). Another approach to perform the same task is using Binary Search.  

Binary Search Approach: 

Binary Search is a searching algorithm used in a sorted array by repeatedly dividing the search interval in half. The idea of binary search is to use the information that the array is sorted and reduce the time complexity to O(Log n). 

Binary Search Algorithm: The basic steps to perform Binary Search are:

  • Sort the array in ascending order.
  • Set the low index to the first element of the array and the high index to the last element.
  • Set the middle index to the average of the low and high indices.
  • If the element at the middle index is the target element, return the middle index.
  • If the target element is less than the element at the middle index, set the high index to the middle index – 1.
  • If the target element is greater than the element at the middle index, set the low index to the middle index + 1.
  • Repeat steps 3-6 until the element is found or it is clear that the element is not present in the array.
     

Binary Search Algorithm can be implemented in the following two ways

  1. Iterative Method
  2. Recursive Method

1. Iteration Method

    binarySearch(arr, x, low, high)
        repeat till low = high
               mid = (low + high)/2
                   if (x == arr[mid])
                   return mid
   
                   else if (x > arr[mid]) // x is on the right side
                       low = mid + 1
   
                   else                  // x is on the left side
                       high = mid - 1

2. Recursive Method (The recursive method follows the divide and conquer approach) 

    binarySearch(arr, x, low, high)
           if low > high
               return False 
   
           else
               mid = (low + high) / 2 
               if x == arr[mid]
                   return mid
       
               else if x > arr[mid]        // x is on the right side
                   return binarySearch(arr, x, mid + 1, high)
               
               else                        // x is on the left side
                   return binarySearch(arr, x, low, mid - 1)

Iterative C++ code (github):

#include <bits/stdc++.h>
#include <iostream>
using namespace std;

int binarySearch(vector<int> v, int find) {
  int lo = 0, hi = v.size() - 1;
  int mid;
  // This below check covers all cases , so need to check
  // for mid=lo-(hi-lo)/2
  while (hi - lo > 1) {
    int mid = (hi + lo) / 2;
    if (v[mid] < find) {
      lo = mid + 1;
    } else {
      hi = mid;
    }
  }
  if (v[lo] == find) {
    return lo;
  } else if (v[hi] == find) {
    return hi;
  } 
  // Not found
  return -1;
}

int main() {
  vector<int> v = {1, 3, 4, 5, 6};

  cout << binarySearch(v, 1) << endl;
  cout << binarySearch(v, 6) << endl;
  cout << binarySearch(v, 10) << endl;

  return 0;
}

Recursive C++ code (repl):

// C++ program to implement recursive Binary Search
#include <bits/stdc++.h>
using namespace std;

// A recursive binary search function. It returns
// location of x in given array arr[l..r] is present,
// otherwise -1
int binarySearch(int arr[], int l, int r, int x)
{
	if (r >= l) {
		int mid = l + (r - l) / 2;

		// If the element is present at the middle
		// itself
		if (arr[mid] == x)
			return mid;

		// If element is smaller than mid, then
		// it can only be present in left subarray
		if (arr[mid] > x)
			return binarySearch(arr, l, mid - 1, x);

		// Else the element can only be present
		// in right subarray
		return binarySearch(arr, mid + 1, r, x);
	}

	// We reach here when element is not
	// present in array
	return -1;
}

int main(void)
{
	int arr[] = { 2, 3, 4, 10, 40 };
	int x = 10;
	int n = sizeof(arr) / sizeof(arr[0]);
  cout << binarySearch(arr, 0, n - 1, 2) << endl;
  cout << binarySearch(arr, 0, n - 1, 10) << endl;
  cout << binarySearch(arr, 0, n - 1, 22) << endl;
	return 0;
}
Scroll to Top