Binary Search

In this tutorial, you will learn about binary search. Also, you will find working examples of binary search in C, C++, Java and Python.

Given a sorted array of n elements, search for an element x in the array.
A simple approach is to do a Linear Search and find the element in O(n) complexity.
Since the array is already sorted, using the binary search algorithm, the complexity can be reduced to O(log n).

Binary Search Algorithm¶

1. Compare x with the middle element of the array
2. If it is a match, the index of the middle element is returned
3. Else if x is greater than the middle element, then x can only lie in right half subarray after the middle element. So we repeat the process for the right half.
4. Else x will lie in the left half, so the process is repeated for the left half.

Recursive Implementation of Binary Search¶

C

  // C program to implement recursive Binary Search 
  #include <stdio.h> 

  // 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 n = sizeof(arr) / sizeof(arr[0]); 
      int x = 10; 
      int result = binarySearch(arr, 0, n - 1, x); 
      (result == -1) ? printf("Element is not present in array") 
                  : printf("Element is present at index %d", 
                              result); 
      return 0; 
  }

C++

  // 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]); 
      int result = binarySearch(arr, 0, n - 1, x); 
      (result == -1) ? cout << "Element is not present in array"
                  : cout << "Element is present at index " << result; 
      return 0; 
  }

Python

  # Python3 Program for recursive binary search. 

  # Returns index of x in arr if present, else -1 
  def binarySearch (arr, l, r, x): 

      # Check base case 
      if r >= l: 

          mid = l + (r - l) // 2

          # If 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 
          elif arr[mid] > x: 
              return binarySearch(arr, l, mid-1, x) 

          # Else the element can only be present  
          # in right subarray 
          else: 
              return binarySearch(arr, mid + 1, r, x) 

      else: 
          # Element is not present in the array 
          return -1

  # Driver Code 
  arr = [ 2, 3, 4, 10, 40 ] 
  x = 10

  # Function call 
  result = binarySearch(arr, 0, len(arr)-1, x) 

  if result != -1: 
      print ("Element is present at index % d" % result) 
  else: 
      print ("Element is not present in array")

Java

  // Java implementation of recursive Binary Search 
  class BinarySearch { 
      // Returns index of x if it is present in arr[l.. 
      // r], else return -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; 
      } 

      // Driver method to test above 
      public static void main(String args[]) 
      { 
          BinarySearch ob = new BinarySearch(); 
          int arr[] = { 2, 3, 4, 10, 40 }; 
          int n = arr.length; 
          int x = 10; 
          int result = ob.binarySearch(arr, 0, n - 1, x); 
          if (result == -1) 
              System.out.println("Element not present"); 
          else
              System.out.println("Element found at index " + result); 
      } 
  }

Iterative Implementation of Binary Search¶

C

  // C program to implement iterative Binary Search 
  #include <stdio.h> 

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

          // Check if x is present at mid 
          if (arr[m] == x) 
              return m; 

          // If x greater, ignore left half 
          if (arr[m] < x) 
              l = m + 1; 

          // If x is smaller, ignore right half 
          else
              r = m - 1; 
      } 

      // if we reach here, then element was 
      // not present 
      return -1; 
  } 

  int main(void) 
  { 
      int arr[] = { 2, 3, 4, 10, 40 }; 
      int n = sizeof(arr) / sizeof(arr[0]); 
      int x = 10; 
      int result = binarySearch(arr, 0, n - 1, x); 
      (result == -1) ? printf("Element is not present"
                              " in array") 
                  : printf("Element is present at "
                              "index %d", 
                              result); 
      return 0; 
  }

C++

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

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

          // Check if x is present at mid 
          if (arr[m] == x) 
              return m; 

          // If x greater, ignore left half 
          if (arr[m] < x) 
              l = m + 1; 

          // If x is smaller, ignore right half 
          else
              r = m - 1; 
      } 

      // if we reach here, then element was 
      // not present 
      return -1; 
  } 

  int main(void) 
  { 
      int arr[] = { 2, 3, 4, 10, 40 }; 
      int x = 10; 
      int n = sizeof(arr) / sizeof(arr[0]); 
      int result = binarySearch(arr, 0, n - 1, x); 
      (result == -1) ? cout << "Element is not present in array"
                  : cout << "Element is present at index " << result; 
      return 0; 
  }

Python

  # Python3 code to implement iterative Binary  
  # Search. 

  # It returns location of x in given array arr  
  # if present, else returns -1 
  def binarySearch(arr, l, r, x): 

      while l <= r: 

          mid = l + (r - l) // 2; 

          # Check if x is present at mid 
          if arr[mid] == x: 
              return mid 

          # If x is greater, ignore left half 
          elif arr[mid] < x: 
              l = mid + 1

          # If x is smaller, ignore right half 
          else: 
              r = mid - 1

      # If we reach here, then the element 
      # was not present 
      return -1

  # Driver Code 
  arr = [ 2, 3, 4, 10, 40 ] 
  x = 10

  # Function call 
  result = binarySearch(arr, 0, len(arr)-1, x) 

  if result != -1: 
      print ("Element is present at index % d" % result) 
  else: 
      print ("Element is not present in array")

Java

  // Java implementation of iterative Binary Search 
  class BinarySearch { 
      // Returns index of x if it is present in arr[], 
      // else return -1 
      int binarySearch(int arr[], int x) 
      { 
          int l = 0, r = arr.length - 1; 
          while (l <= r) { 
              int m = l + (r - l) / 2; 

              // Check if x is present at mid 
              if (arr[m] == x) 
                  return m; 

              // If x greater, ignore left half 
              if (arr[m] < x) 
                  l = m + 1; 

              // If x is smaller, ignore right half 
              else
                  r = m - 1; 
          } 

          // if we reach here, then element was 
          // not present 
          return -1; 
      } 

      // Driver method to test above 
      public static void main(String args[]) 
      { 
          BinarySearch ob = new BinarySearch(); 
          int arr[] = { 2, 3, 4, 10, 40 }; 
          int n = arr.length; 
          int x = 10; 
          int result = ob.binarySearch(arr, x); 
          if (result == -1) 
              System.out.println("Element not present"); 
          else
              System.out.println("Element found at "
                              + "index " + result); 
      } 
  }

Binary Search Complexities¶

Time Complexity = O(log n)

Space Complexity = O(1) for Iterative Binary Search and O(log n) for Recursive Binary Search

Binary Search Applications¶

It is generally used when the array elements are ordered or sorted.
Sometimes, an array isn't sorted but the number of search queries is very high. Then instead of doing Linear Search for each time, the array is sorted once initially and then binary search is performed for each query.