Binary Search Algorithm

Open-Source Internship opportunity by OpenGenus for programmers. Apply now.

Reading time: 15 minutes | Coding time: 6 minutes

Binary Search algorithm is an efficient comparison based search algorithm where the key idea is to reduce the size of search space by half in every iteration by exploiting a restriction on the search space that it is in sorted order. When suitable, binary search is choose over other search algorithms.

The key idea is that is a list is sorted and we compared a number with a random number from the list, we can say whether the potential match lies on the left or the right of the number.

When the number is the middle element, then we can reduce the number of potential matches by half.

Algorithm

The steps involved in Binary search algorithm are:
Pre-condition: The element list must be sorted.

Step 1: Find middle element of the array.
Step 2: Compare the value of the middle element with the target value.
Step 3: If they match, it is returned.
Step 4: If the value is less or greater than the target, the search continues in the lower or upper half of the array accordingly.
Step 5: The same procedure as in step 2-4 continues, but with a smaller part of the array. This continues until the target element is found or until there are no elements left.

Example

Consider the following sorted list in which we want to find 6:

-1 3 3 6 11 12 16 17 18 19

We chose to compare with the middle element 12 with 6. As 12 > 6, 6 will lies at the left side of 12.

The potential numbers are:

-1 3 3 6 11

We compare 6 with the middle element 3. As 3 < 6, 6 will be at the right side of 3.

The potential numbers are:

6 11

We compare our target 6 with the middle element 6. As 6 == 6, we found our target.

Complexity

Worst case time complexity: O(log N)
Average case time complexity: O(log N)
Best case time complexity: O(1)
Space complexity: O(1)

As the search space is reduced by half each time until all elements are eliminated, the worst case is O(log N).

Implementations

Implementation of Linear search algorithm in 16 languages that includes C, C++, Java, C#, Racket, Go, Haskell, JavaScript, Kotlin, PHP, Ruby, Rust, Scala, Shell and Swift.

C
C++
Java
C#
Racket
Go
Haskel
JavaScript
Kotlin
PHP
Python
Ruby
Rust
Scala
Shell
Swift

Tab 1


#include <stdio.h>
/*
 * Part of Cosmos by OpenGenus Foundation
*/
int recursiveBinarySearch(int arr[], int l, int r, int x)
{
   if (r >= l)
   {
        int mid = l + (r - l)/2;
        if (arr[mid] == x)  
            return mid;
        if (arr[mid] > x) 
             return recursiveBinarySearch(arr, l, mid-1, x);       
         return recursiveBinarySearch(arr, mid+1, r, x);
   }
   return -1;
}
int binarySearch(int arr[], int l, int r, int x)
{
  while (l <= r)
  {
    int mid = l + (r-l)/2;
    if (arr[mid] == x) 
        return mid;  
    if (arr[mid] < x) 
        l = mid + 1; 
    else
         r = mid - 1; 
  }
  return -1; 
} 
int main(void)
{
   int arr[] = {1, 2, 3, 5};
   int size = sizeof(arr)/ sizeof(arr[0]);
   int find = 3;
   printf("Position of %d is %d\n", find, recursiveBinarySearch(arr, 0, size-1, find));
   printf("Position of %d is %d\n", find, binarySearch(arr, 0, size-1, find));
   return 0;
}

Tab 2


/* Part of Cosmos by OpenGenus Foundation */
#include <iostream>
#include <vector>
#include <cstdlib>
#include <algorithm>
using namespace std;
/* Utility functions */
void fill(vector &v) {
    for(int i=0;i &v) {
    for(int i=0;i &v, int key) {
    int m; 
    int l=0,r=v.size();
    while(r-l >1) {
        m=l+(r-l)/2;
        if( v[m] > key) 
            r=m;
        else 
            l=m;
    }  
    if ( v[l] == key) 
        return l;
    else 
        return -1;
}
/* Driver program */
int main() {
    int size;
    cout << "Set array size:";
    cin >> size;  
    vector v(size);
    fill(v);
    cout << "Array (sorted) : ";
    sort(v.begin(),v.end());    
    printarr(v);   
    cout << "Search for (input search key) : ";
    int key;
    cin >> key;   
    cout << "Found " << key << " at index "<< binary_search(v,key) << endl;
}

Tab 3


/*
 * Part of Cosmos by OpenGenus Foundation
*/
class Search
{
    static int recursiveBinarySearch(int arr[], int l, int r, int x)
    {
        if (r>=l)
        {
            int mid = l + (r - l)/2;
             if (arr[mid] == x)
               return mid;
             if (arr[mid] > x)
               return recursiveBinarySearch(arr, l, mid-1, x);
        return recursiveBinarySearch(arr, mid+1, r, x);
    }
    return -1;
}  
static int binarySearch(int arr[], int l, int r, int x)
{
    while (l <= r)
    {
        int mid = l + (r-l)/2;
        if (arr[mid] == x) 
            return mid;  
        if (arr[mid] < x) 
            l = mid + 1; 
        else
            r = mid - 1; 
    }
    return -1; 
}
 public static void main(String args[])
{
    int arr[] = {1, 2, 3, 5};
    int size = arr.length;
    int find = 3;
    System.out.println("Position of "+find+" is "+recursiveBinarySearch(arr,0,size-1,find));
    System.out.println("Position of "+find+" is "+binarySearch(arr,0,size-1,find));
}

}

Tab 4


using System;
namespace binary_search
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] arr = new int[10]
                {1, 10, 14, 26, 39, 44, 68, 77, 81, 92};
            Console.WriteLine("Array: ");
            for(int i=0; i<10; i++)
            {
                Console.Write(arr[i] + "  ");
            }
            Console.WriteLine("\nInput -1 to terminate program");
            int find = 0;
            int res;
            while(find != -1)
            {
                Console.Write("Input number to search: ");
                find = Int32.Parse(Console.ReadLine());
                if ((res = binarySearch(arr, find)) != -1)
                    Console.WriteLine($" + Found number {find} at index {res}");     
                else
                    Console.WriteLine(" - Number not found!");
            }
        }
        static int binarySearch(int[] arr, int key)
        {
            int low = 0;
            int high = arr.Length - 1;
            while (low <= high)
            {
                int midIndex = low + (high - low) / 2;
                if (arr[midIndex] == key)
                    return midIndex;
                else if (key > arr[midIndex])
                    low = midIndex + 1;
                else
                    high = midIndex - 1;
            }
            return -1;
        }
    }
}

Tab 5


#lang racket
(define (binary-search val l)
  (cond [(empty? l) false]
        [(equal? val (first l)) true]
        [else
         (define midpoint (quotient (length l) 2))
         (define value-at-midpoint (first (drop l midpoint)))
         (if (>= val value-at-midpoint)
             (binary-search val (drop l midpoint))
             (binary-search val (take l midpoint)))]))
(define test-list (build-list 10 values))
(display "Searching for 4 should be #t: ")
(displayln (binary-search 4 test-list))
(display "Searching for 1 should be #t: ")
(displayln (binary-search 1 test-list))
(display "Searching for 8 should be #t: ")
(displayln (binary-search 8 test-list))
(display "Searching for 11 should be #f: ")
(displayln (binary-search 11 test-list))

Tab 6


package main
import "fmt"
import "sort"
// Part of Cosmos by OpenGenus Foundation
func binarySearch(data []int, value int) int {
	startIndex := 0
	endIndex := len(data) - 1
	for startIndex <= endIndex {
		midIndex := (startIndex + endIndex) / 2
		mid := data[midIndex]
		if mid < value {
			endIndex = midIndex - 1
		} else if mid > value {
			startIndex = midIndex + 1
		} else {
			return midIndex
		}
	}
	return -1
}
func buildInSearch(data []int, value int) int {
	i := sort.Search(len(data), func(i int) bool { return data[i] >= value })
	if i < len(data) && data[i] == value {
		return i
	}
	return -1
}
func main() {
	values := []int{1, 2, 3, 4, 5, 12, 35, 30, 46, 84}
	fmt.Println("custom implementation")
	fmt.Println(binarySearch(values, 5))
	fmt.Println(binarySearch(values, 7))
	fmt.Println("use build-in search function")
	fmt.Println(buildInSearch(values, 5))
	fmt.Println(buildInSearch(values, 13))
}

Tab 7


{-
    Part of Cosmos by OpenGenus Foundation
-}
binarySearch :: [Int] -> Int -> Int -> Int -> Int
binarySearch arr val low high
    | high < low = -1
    | arr!!mid < val = binarySearch arr val (mid+1) high
    | arr!!mid > val = binarySearch arr val low (mid-1)
    | otherwise = mid
    where
        mid = (low + high) `div` 2
main = do
    let arr = [3,5,12,56,92,123,156,190,201,222]
    let number = 12
    putStrLn("Position of "
             ++ show(number)
             ++ " is "
             ++ show(binarySearch arr number 0 ((length arr) - 1)))

Tab 8


  function binarySearch(array, key) {
    var lo = 0,
        hi = array.length - 1,
        mid,
        element;
    while (lo <= hi) {
        mid = Math.floor((lo + hi) / 2, 10);
        element = array[mid];
        if (element < key) {
            lo = mid + 1;
        } else if (element > key) {
            hi = mid - 1;
        } else {
            return mid;
        }
    }
    return -1;
}

Tab 9


// Part of Cosmos by OpenGenus Foundation
fun > binarySearch(a: Array, key: T): Int? {
    var lowerBound = 0
    var upperBound = a.size
    while (lowerBound < upperBound) {
        val middleIndex = lowerBound + (upperBound - lowerBound) / 2
        when {
            a[middleIndex] == key -> return middleIndex
            a[middleIndex] < key -> lowerBound = middleIndex + 1
            else -> upperBound = middleIndex
        }
    }
    return null
}
fun main(args: Array) {
    val sample: Array = arrayOf(13, 17, 19, 23, 29, 31, 37, 41, 43)
    val key = 23
    val result = binarySearch(sample, key)
    println(when (result) {
        null -> "$key is not in $sample"
        else -> "Position of $key is $result"
    })
}

Tab 10


/*
 * Part of Cosmos by OpenGenus Foundation
 *
 * @param array $array
 * @param int   $low
 * @param int   $high
 * @param int   $search
 * @return int
 */
function binarySearch(array $array, $low, $high, $search)
{
    if ($high >= $low) {
        $middle = (int) ($low + ($high - $low) / 2);
        if ($array[$middle] === $search) {
            return $middle;
        } else if ($array[$middle] > $search) {
            return binarySearch($array, $low, $middle - 1, $search);
        } else {
            return binarySearch($array, $middle + 1, $high, $search);
        }
    }
    return -1;
}
if (!isset($dontPrintBinarySearchTest)) {
    echo sprintf(
        "Position of %d is %d\n",
        $search = 33, binarySearch($array = [7, 11, 13, 33, 66], 0, count($array) - 1, $search)
    );
}

Tab 11


'''
Part of Cosmos by OpenGenus Foundation
'''
def binarySearchRecursive(arr, l, r, x):
    if r >= l:
        mid = l + int((r - l) / 2)
        if arr[mid] == x:
            return mid
        elif arr[mid] > x:
           return binarySearchRecursive(arr, l, mid - 1, x)
        else:
            return binarySearchRecursive(arr, mid + 1, r, x)
    else:
        return -1
def binarySearchLoop(arr, l, r, x):
    while l <= r:
        mid = l + int((r - l) / 2)
        if arr[mid] == x:
            return mid
        elif arr[mid] > x:
            r = mid - 1
        else:
            l = mid + 1
    return -1
arr = [1, 2, 3, 5]
find = 3
print("Position of ", find, " is ", binarySearchLoop(arr, 0, len(arr) - 1, find))
print("Position of ", find, " is ", binarySearchRecursive(
    arr, 0, len(arr) - 1, find))

Tab 12


#   Part of Cosmos by OpenGenus Foundation
def binary_search(arr, l, r, x)
  return -1 if x.nil?
  if r >= l
    mid = (l + r) / 2
    if arr[mid] == x
      mid
    elsif arr[mid] > x
      binary_search(arr, l, mid - 1, x)
    else
      binary_search(arr, mid + 1, r, x)
    end
  end
end
arr = [3, 5, 12, 56, 92, 123, 156, 190, 201, 222]
number = 12
puts "Position of #{number} is #{binary_search(arr, 0, arr.length - 1, number)}"

Tab 13


  fn main() {
    let nums = vec![1, 3, 5, 7, 9];
    let find_me = 5;
    let result = binary_search(&nums, find_me, 0, nums.len());
    println!("Given Array: {:?}", nums);
    match result {
        Some(index) => println!("Searched for {} and found index {}.", find_me, index),
        None => println!("Searched for {} but found no occurrence.", find_me),
    }
}
fn binary_search(nums: &[i64], search_value: i64, left: usize, right: usize) -> Option {
    let mut left: usize = left;
    let mut right: usize = right;
    while left <= right {
        let middle = (left + right) / 2;
        if middle == nums.len() {
            break;
        }
        if nums[middle] == search_value {
            return Some(middle);
        } else if nums[middle] < search_value {
            left = middle + 1;
        } else if nums[middle] > search_value && middle != 0 {
            right = middle - 1;
        } else {
            break;
        }
    }
    None
}

Tab 14


package opengenus.cosmos.sorting
import scala.annotation.tailrec
object BinarySearch {  
  trait SearchResult
  case class Found(i: Int) extends SearchResult
  case object NotFound extends SearchResult
  def apply[T](element: T)(collection: List[T])(implicit ord: Ordering[T]): SearchResult = {
    @tailrec
    def binarySearchStep(start: Int, end: Int): SearchResult = {
      val mid = start + (end - start) / 2
      val midValue = collection(mid) 
      if(midValue == element) Found(mid)
      else if(start > end) NotFound
      else if(ord.gt(element, midValue)) binarySearchStep(mid+1, end)
      else binarySearchStep(start, mid-1)
    } 
    binarySearchStep(0, collection.size-1)
  }
}

Tab 15


#!/bin/bash
#read Limit
echo Enter array limit
read limit
#read Elements
echo Enter elements
n=1
while [ $n -le $limit ]
do
	read num
	eval arr$n=$num
	n=`expr $n + 1`
done
#read Search Key Element
echo Enter key element
read key
low=1
high=$n
found=0
#Find middle element
#for(( low=0,found=0,high=$((n-1)) ; l<=u ; ))
while [ $found -eq 0 -a $high -gt $low ]
do
	mid=`expr \( $low + $high \) / 2`
	eval t=\$arr$mid
	if [ $key -eq $t ] #Compare the value of the middle element with the target value. MATCH
	then
		found=1
	elif [ $key -lt $t ] #Compare the value of the middle element with the target value. LESS
	then
		high=`expr $mid - 1`
	else
		low=`expr $mid + 1` #Compare the value of the middle element with the target value. GREATER
	fi
done # Repeat
if [ $found -eq 0 ]
then
	echo Unsuccessfull search
else
	echo Successfull search
fi

Tab 16


//  binary_search.swift
//  Created by iraniya on 10/4/17.
// Part of Cosmos by OpenGenus Foundation
/*
 Binary Search
 Recursively splits the array in half until the value is found.
 If there is more than one occurrence of the search key in the array, then
there is no guarantee which one it finds.
Note: The array must be sorted!
*/
import Foundation
// The recursive version of binary search.
public func binarySearch(_ a: [T], key: T, range: Range) -> Int? {
    if range.lowerBound >= range.upperBound {
        return nil
    } else {
        let midIndex = range.lowerBound + (range.upperBound - range.lowerBound) / 2
        if a[midIndex] > key {
            return binarySearch(a, key: key, range: range.lowerBound ..< midIndex)
        } else if a[midIndex] < key {
            return binarySearch(a, key: key, range: midIndex + 1 ..< range.upperBound)
        } else {
            return midIndex
        }
    }
}
/*
 The iterative version of binary search.
 Notice how similar these functions are. The difference is that this one
 uses a while loop, while the other calls itself recursively.
*/
public func binarySearch(_ a: [T], key: T) -> Int? {
    var lowerBound = 0
    var upperBound = a.count
    while lowerBound < upperBound {
        let midIndex = lowerBound + (upperBound - lowerBound) / 2
        if a[midIndex] == key {
            return midIndex
        } else if a[midIndex] < key {
            lowerBound = midIndex + 1
        } else {
            upperBound = midIndex
        }
    }
    return nil
}
let numbers = [1,2,3,4,5]
let key = 5
var find = binarySearch(numbers, key: key, range: 0 ..< numbers.count)  // gives 13
print("Position of \(key) is \(find)")
//printf("Position of %d is %d\n", find, binarySearch(arr, 0, size-1, find));

Optimizations

Exponential search extends binary search to unbounded lists.
Factional cascading speeds up binary searches for the same value in multiple arrays, efficiently solving a series of search problems in computational geometry and numerous other fields
Interpolation search: Instead of calculating the midpoint, interpolation search estimates the position of the target value, taking into account the lowest and highest elements in the array as well as length of the array. This is only possible if the array elements are numbers. It works on the basis that the midpoint is not the best guess in many cases. For example, if the target value is close to the highest element in the array, it is likely to be located near the end of the array. When the distribution of the array elements is uniform or near uniform, it makes O(log log N) comparisons
Noisy binary search algorithms solve the case where the algorithm cannot reliably compare elements of the array. For each pair of elements, there is a certain probability that the algorithm makes the wrong comparison. Noisy binary search can find the correct position of the target with a given probability that controls the reliability of the yielded position

Applications

Implementing a switch case construct in a virtual machine where the case labels are individual integers. Matching can be achieved in logarithmic time.
Doing fast substring lookup using suffix arrays, which contain all the suffixes of the set of searchable strings in lexiographic ordering
Finding numerical solutions to an equation
In R programming language there is a package data.table which uses binary search.
git bisect: Binary search can be used to debug with Git.
Semiconductor test programs used for measuring digital timing or analog levels make extensive use of binary search.
figuring out resource requirements for a large system. one could try running load tests on the system and binary search for the minimum amount of CPUs required to handle a predicted load
cherry picking a bad code change from a release candidate.
debugging a linear piece of code