# Binary Search Algorithm

#### Search Algorithms binary search Algorithms Get FREE domain for 1st year and build your brand new site

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
• 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);
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
{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: ");
if ((res = binarySearch(arr, find)) != -1)
Console.WriteLine(\$" + Found number {find} at index {res}");
else
}
}
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
echo Enter array limit
echo Enter elements
n=1
while [ \$n -le \$limit ]
do
eval arr\$n=\$num
n=`expr \$n + 1`
done
echo Enter key element
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

1. Exponential search extends binary search to unbounded lists.
2. 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
3. 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
4. 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 #### Alexa Ryder

Hi, I am creating the perfect textual information customized for learning. Message me for anything.