Binary Search

The binary search algorithm in data structure | Binary search is an efficient algorithm for finding an item from a sorted list or array of items. Sometimes it is also known as half-interval search, logarithmic search, or binary chop. 

Condition:- The array must be sorted in ascending order.

The binary search algorithm cannot be applied to unsorted arrays. This algorithm can be used when the list or array has terms occurring in order of increasing size (for instance: if the terms are numbers, they are listed from smallest to largest; if they are words, they are listed in lexicographic, or alphabetic, order). If the array or list is not sorted then before applying the binary search algorithm, first sort the array or list.

It can be written in two ways. These are,
a) Recursive approach
b) Iterative approach


Binary Search using Recursion

In the recursive approach, the recursion technique is used. It is an example of the divide and conquers technique where bigger problems are divided into smaller problems. Like all divide and conquer algorithms binary search first divides the large array into smaller sub-arrays and then solves it recursively.  we see it in detail.

Binary Search Algorithm in Recursive Approach

a) Take an array, initial index, size, and search key.
b) Find the middle term.
c) if middle term == search key then return index.
d) if middle term > search key then apply recursive call on the first half of the array.
e) else apply a recursive call on the second half of the array.
f) Repeat the process until the search key is not matched.
g) If not matched then return -1.

It can be written as,

int binarySearch(arr, low, high, key) {
    if (high >= low) {
        int mid = low + (high - low) / 2; 
        if (arr[mid] == key) return mid; 
        if (arr[mid] > key) 
            return binarySearch(arr, low, mid - 1, key); 
        return binarySearch(arr, mid + 1, high, key); 
    }
    return -1; 
}

The time complexity of this algorithm = O(log n)

How Recursive approach works?

In binary search using a recursive approach, we split the array from the middle into two subarrays of the same size or where one of these smaller lists has one fewer term than the other. Let us understand it through an example.

Array = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};

Example

Assume the search term = 40. Then the steps in this algorithm,

  • Find the middle term of the array. If the size of the array is odd then middle-index = (size – 1)/2 else middle-index = size/2. In our example, middle index = 10/2 = 5, and middle term is array[3] = 60
  • Compare the middle term and search term. If the middle term > search term then it may exist in the first portion of the array else in the second portion of the array. Since 60 > 40 therefore search terms may exist only in the first portion of the array.
  • Split the array into two parts from the middle index. The subarr1 = {10, 20, 30, 40, 50} and subarr2 = {60, 70, 80, 90, 100}.
  • Since the array is sorted and 60 > 40, therefore search terms may exist only in the first sub-array. Forgot about the second sub-array, no use of it, only the first sub-array is required for the next step. Now, assume the original array = {10, 20, 30, 40, 50}, and search term = 40.
  • Repeat the same process with the first sub-array. Find the middle term. The middle index = (5-1)/2 = 2, middle term is array[2] = 30
  • Compare middle term with a search term, 30 < 40 therefore it may exist only in the second portion.
  • Split array into two subarrays from the middle index. The new sub arrays are:- subarr1 = {10, 20} and subarr2 = {30, 40, 50}. Only subarr2 will be considered for the next steps, no use of subarr1. Now, assume array = {30, 40, 50} and search term = 40. Repeat the process.
  • Find the middle term. The middle index = (3-1)/2 = 1 and the middle term is array[1] = 40.
  • Compare the middle term and search term. Currently, both are equal and a match is found.

Binary Search Example using Recursion

Let us see an example of this algorithm using recursion in different programming languages. The logic remains the same in every programming language.

C Program for Binary Search using Recursion

#include <stdio.h>
// function for binary search
/* if match found then return index of search key
   else return -1 */
int binarySearch(int arr[], int low, int high, int key) {
  if (high >= low) {
    // find middle index
    int mid = low + (high - low) / 2; 
     
    // find middle term and compare
    if (arr[mid] == key) return mid; // key found 
     
    // If key is smaller than middle term, then 
    // it can only be present in left subarray 
    if (arr[mid] > key) 
      return binarySearch(arr, low, mid - 1, key); 
    
    // Else the key can only be present 
    // in right subarray 
    return binarySearch(arr, mid + 1, high, key); 
  } 
     
  // key not found
  return -1; 
}
// main function
int main()
{
  int array[] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
  int key = 40; // search key

  // find the array size 
  int size = sizeof(array)/sizeof(array[0]);

  // search key
  int index = binarySearch(array, 0, size, key);
  
  if(index == -1)
    printf("%d Not Found\n", key);
  else
    printf("%d Found at Index = %d\n", key, index);

  return 0;
}

Output:-

40 Found at Index = 3

Also See:- Program in C++

Java Program for Binary Search using Recursion

public class Search {

   public static void main(String[] args) {
      int arr[] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
      int key = 40; // search key

      // binary search
      int index = binarySearch(arr, 0, arr.length, key);

      // display result
      if (index == -1)
         System.out.println(key + " not Found.");
      else
         System.out.println(key + " Found at Index = " + index);
   }

   // Method for binary search
   /* if match found then return index of search key
      else return -1 */
   public static int binarySearch(int[] arr, int low, 
                       int high, int key) {
      if (high >= low) {
         // find middle index
         int mid = low + (high - low) / 2; 
     
         // find middle term and compare
         if (arr[mid] == key) return mid; // key found 
     
         // If key is smaller than middle term, then 
         // it can only be present in left subarray 
         if (arr[mid] > key) 
            return binarySearch(arr, low, mid - 1, key); 
     
         // Else the key can only be present 
         // in right subarray 
         return binarySearch(arr, mid + 1, high, key); 
      } 
     
      // key not found
      return -1; 
   }

}

Output:-

40 Found at Index = 3

Python Program for Binary Search using Recursion

# Python program for binary search using recursion

def BinarySearch(arr, low, high, key):  #user-defined function
    if high >= low:  #check base case
        mid = (high + low) // 2
        if (arr[mid] == key):
            return mid
        elif (arr[mid] > key):
            return BinarySearch(arr, low, mid - 1, key)
        else:
            return BinarySearch(arr, mid + 1, high, key)
    else:
        return -1

arr = [ 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 ]  #array
key = 40  #search key

# calling function
result = BinarySearch(arr, 0, len(arr)-1, key)

# display result
if result != -1:
    print(key, "Found at index", str(result))
else:
    print(key, "not Found")

Output:-

40 Found at index 3


Binary Search using Iterative approach

In this approach, instead of calling the method recursively, we use iteration to traverse the array and find the search key. Both approaches are quite the same, with two differences in implementation. 

In a recursive method, there is no loop, and rather than passing the new values to the next iteration of the loop, it passes them to the next recursion. In the iterative method, the iterations can be controlled through the looping conditions, while in the recursive method, the maximum and minimum are used as the boundary condition. 

Binary search algorithm in data structure using Iterative approach

To search for the integer x in the list/array a1, a2 , … ,an , where list/array is in ascending order (a1 < a2 <  ··· < an)

  • begin by comparing x with the middle term am of the list/array, where m = ⌊(n + 1)/2⌋. 
  • If x > am, the search for x is restricted to the second half of the list, which is am+1, am+2, …, an.
  • If x is not greater than am, the search for x is restricted to the first half of the list, which is a1, a2, …, am.
  • The search has now been restricted to a list with no more than ⌊n/2⌋ elements. 
  • Using the same procedure, compare x to the middle term of the restricted list. 
  • Then restrict the search to the first or second half of the list. 
  • Repeat this process until a list with one term is obtained. 
  • Then determine whether this term is x.

The algorithm can be written as,

int binary search (a: array, low, high,  x: search-key) {
   i := low; // i is left endpoint of search interval
   j := high; // j is right endpoint of search interval
   while (i < j) {
      m := ⌊(i+j)/2⌋
      if x > a[m] then i := m+1
      else j := m
   }
   if x=a[i] then location := i
   else location := -1
   return location
}

Code For Binary Search

Let us see examples using an iteration approach in different programming languages. The logic remains the same in every programming language.

C Program

#include <stdio.h>
// function for binary search
/* if match found then return index of search key
   else return -1 */
int binarySearch(int arr[], int low, int high, int key) {
  int i = low; // left index
  int j = high; // right index
  int mid = 0;
      
  while(i < j) {
    // find middle index
    mid = (i+j) / 2;

    // compare search key and middle term
    if(key > arr[mid]) 
      i = mid + 1;
    else
      j = mid;
  }
      
  // when i==j
  if(key == arr[i]) 
    return i; // key found

  return -1; // key not found 
}
// main function
int main()
{
  int array[] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
  int key = 40; // search key

  // find the size array
  int size = sizeof(array)/sizeof(array[0]);

  // search key
  int index = binarySearch(array, 0, size, key);

  if(index == -1)
    printf("%d Not Found\n", key);
  else
    printf("%d Found at Index = %d\n", key, index);

  return 0;
}

Output:-

40 Found at Index = 3

Java Program

public class Search {

  public static void main(String[] args) {
    int arr[] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
    int key = 40; // search key

    // binary search
    int index = binarySearch(arr, 0, arr.length, key);
    // int index = binarySearch(arr, key);

    // display result
    if (index == -1)
      System.out.println(key + " not Found.");
    else
      System.out.println(key + " Found at Index = " + index);

  }
  
  public static int binarySearch(int[] arr, int low, 
                            int high, int key) {
    int i = low; // left index
    int j = high; // right index
    int mid = 0;
    
    while(i < j) {
      // find middle index
      mid = (i+j)/2;
      
      // compare search key and middle term
      if(key > arr[mid]) 
        i = mid + 1;
      else
        j = mid;
    }
    
    // when i==j
    if(key == arr[i]) return i; // key found
      return -1; // key not found
  }
}

Output:-

40 Found at Index = 3

Python Program

# Python program for binary search using recursion

def BinarySearch(arr, key):  #user-defined function
    low = 0
    high = len(arr) - 1
    mid = 0
 
    while low <= high:
        mid = (high + low) // 2
        if arr[mid] < key:
            low = mid + 1
        elif arr[mid] > key:
            high = mid - 1
        else:
            return mid
    return -1

arr = [ 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 ]  #array
key = int(input('Enter search key: '))  #search key

# calling function
result = BinarySearch(arr, key)

# display result
if result != -1:
    print(key, "Found at index", str(result))
else:
    print(key, "not Found")

Output:-

Enter search key: 10
10 Found at index 0

Enter search key: 60
60 Found at index 5

Binary Search Time Complexity

Best-case
time complexity 
O(1)When the search key present at the center
(middle term) of the array/list.
Worst-case
time complexity
O(log n)When the search key is not available or at
the extremity of the list.

In the iterative method, the space complexity would be O(1). While in the recursive method, the space complexity would be O(log n). 

For the small arrays linear search algorithm gives better performance compared to this algorithm, but for the large arrays if the array is in sorted order then this algorithm gives better performance compared to the linear search algorithm. 

There are specialized data structures designed for fast searching, such as hash tables, that can be searched more efficiently than this algorithm. However, it can be used to solve a wider range of problems, such as finding the next-smallest or next-largest element in the array relative to the target even if it is absent from the array.

Q) Binary search algorithm cannot be applied to?
a) Sorted linked list
b) Sorted binary trees
c) Sorted linear array
d) Pointer array

[bg_collapse view=”button-blue” color=”#fff” icon=”eye” expand_text=”Show Answer” collapse_text=”Show Less” ]

Ans:- a) Sorted linked list

The binary search algorithm is based on the logic of reducing input size by half in every step until the search succeeds or input gets exhausted. But in the case of the Linked list, we don’t have indexes to access items. 

[/bg_collapse]

If you enjoyed this post, share it with your friends. Do you want to share more information about the topic discussed above or you find anything incorrect? Let us know in the comments. Thank you!

Leave a Comment

Your email address will not be published. Required fields are marked *