Introduction

Binary Search is a searching algorithm that is used to search an element in a sorted list or array. It works by repeatedly dividing the search interval in half. The idea is to begin by comparing the middle element of the array with the target value. If the target value matches the middle element, the search ends successfully. Otherwise, depending on whether the target value is greater or less than the middle element, the search continues either in the left or the right half of the array respectively. It is a widely-used algorithm in computer science due to its efficiency in searching.

Implementation


(* Binary Search *)

let rec binary_search a value low high =
  if high = low then
    if a.(low) = value then
      low
    else
      raise Not_found
  else let mid = (low + high) / 2 in
    if a.(mid) > value then
      binary_search a value low (mid - 1)
    else if a.(mid) < value then
      binary_search a value (mid + 1) high
    else
      mid

The binary_search algorithm takes in four parameters: an array a, the value to be searched for in the array, the low index and the high index of the search interval. It then proceeds based on the value comparison between the middle element and the search value.

Step-by-step Explanation

  1. The algorithm begins with the search interval defined by the low and high indices.
  2. If the low and high indices are the same, the algorithm checks if the element at the low index is equal to the search value. If it is, the algorithm returns the index low, otherwise, it raises a Not_found exception indicating that the element is not in the array.
  3. If the search interval has a length greater than 1 (high > low), the algorithm proceeds to calculate the mid index by taking the average value of the low and high indices: mid = (low + high) / 2.
  4. The algorithm then checks if the value to be searched for is greater than or less than the element at the mid index:
    1. If the mid element is greater than the value, the search interval is partitioned into the left half, and the algorithm is called recursively with the search interval now defined by the low index and (mid - 1) index.
    2. If the mid element is less than the value, the search interval is partitioned into the right half, and the algorithm is called recursively with the search interval now defined by the (mid + 1) index and high index.
    3. If the mid element is equal to the value, then the algorithm returns the index of the mid element.
  5. The algorithm repeats steps 2–4 until the search value is found, or the entire array has been traversed unsuccessfully.

Complexity Analysis

The best-case time complexity for binary search is O(1), which occurs when the target element being searched for is the middle element of the sorted array. The worst-case time complexity is O(log n), whereby the search interval is partitioned into halves at each step of the recursive call until the target element is found or the search space is exhausted. The space complexity for binary search is O(1) as it does not require additional space other than what is used to store the sorted array.