Binary Search Algorithm

Binary search is a search algorithm used to find the position of a value within a sorted array. It begins by comparing an element in the middle of the array with the target value. If the target value matches the element, its position in the array is returned. If the target value is less than the element, the search continues in the lower half of the array. If the target value is greater than the element, the search continues in the upper half of the array. By doing this, the algorithm eliminates the half in which the target value cannot lie in each iteration.

Procedure

Given an array $A$ of $n$ elements with values $A_{0}, A_{1}, A_{2},...,A_{n-1}$ sorted such that $A_{0} \le A_{1} \le A_{2} \le ... \le A_{n-1}$ , and target value $T$ , the following subroutine uses binary search to find the index of $T$ in $A$ .:

Set $L$ to $0$ and $R$ to $n - 1$ ( $n$ being the size of the array).
If $L \gt R$ , the search terminates as unsuccessful.
Set $m$ (the position of the middle element) to the floor of $\frac{L + R}{2}$ , which is the greates integer less than or equal to $\frac{L + R}{2}$ .
If $A_{m} \lt T$ , set $L$ to $m + 1$ and go to step 2.
If $A_{m} \gt T$ , set $R$ to $m - 1$ and go to step 2.
Now $A_{m} = T$ , the search is done; return $m$

This iterative procedure keeps track of the search boundaries with the two variables $L$ and $R$ . The pseudocode is available below:

function binary_search(A, T) is
	n = size(A)
	L := 0
	R := n - 1
	while L <= R do
		m := floor((L + R) / 2)
		if A[m] < T then
			L := m + 1
		else if A[m] > T then
			R := m - 1
		else:
			return m

	return unsuccessful

Implementations

Python

import numpy as np

def binarySearch(A, T):
    n = len(A)
    L = 0
    R = n - 1

    while L <= R:
        m = int(np.floor((L + R) / 2))
        if A[m] < T:
            L = m + 1
        elif A[m] > T:
            R = m - 1
        else:
            return m

    return "Unsuccessful"

# Example
M = np.arange(1, 10, 1)

number = 2
result = binarySearch(M, number)

print(f"The value of {number} is in index [{result}].")

Note: In python, it is necessary to convert the result of the np.floor function because python implicitly converts the integers into float.

Rust

fn binary_search(a: &[i32], t: i32) -> Option<usize> {
    let mut l = 0;
    let mut r = a.len() - 1;

    while l <= r {
        let m = (l + r) / 2;
        if a[m] < t {
            l = m + 1;
        } else if a[m] > t {
            r = m - 1;
        } else {
            return Some(m);
        }
    }
    return None
}

fn main() {
    let arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19];
    let target = 7;

    match binary_search(&arr, target) {
        Some(index) => println!("Found {} at index {}", target, index),
        None => println!("{} not found", target),
    }
}

In Rust, the match keyword is used for pattern matching. It’s similar to a switch statement in other languages, but more powerful.

JavaScript

let binarySearch = function (A, T) {
  let L = 0;
  let R = A.length - 1;

  while (L <= R) {
    let m = Math.floor((L + R) / 2);
    if (A[m] < T) {
      L = m + 1;
    } else if (A[m] > T) {
      R = m - 1;
    } else {
      return m;
    }
  }
  return null;
};

let numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
let target = 4;
let result = binarySearch(numbers, target);

console.log("Found ", target, " in position ", result);

TypeScript

Just for fun

let BinarySearch = function (A: number[], T: number): number | null {
  let L: number = 0;
  let R: number = A.length - 1;

  while (L <= R) {
    let m: number = Math.floor((L + R) / 2);
    if (A[m] < T) {
      L = m + 1;
    } else if (A[m] > T) {
      R = m - 1;
    } else {
      return m;
    }
  }
  return null;
};

let num: number[] = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
let targ: number = 4;
let resul = BinarySearch(num, targ);

console.log("Found ", targ, " in position ", resul);