namespace Algorithms.Search
module BinarySearch =
/// Search the target item in a sorted array.
/// Returns -1 when the target is not found.
/// Time complexity: O(log(sortedData.Length)))
let findIndex target sortedData =
let rec search l r =
let count = r - l
let mid = (l + r) / 2
let midItem = Array.item mid sortedData
match count <= 1, compare midItem target with
| _, 0 -> mid
| true, _ -> -1
| false, -1 -> search mid r
| false, 1 -> search l mid
| _ -> exn () |> raise
search 0 (Array.length sortedData + 1)
Given a sorted array of n elements, write a function to search for the index of a given element (target)
O(log n) Worst Case
O(1) Best Case (If middle element of initial array is the target element)
O(1) For iterative approach
O(1) For recursive approach if tail call optimization is used, O(log n) due to recursion call stack, otherwise
arr = [1,2,3,4,5,6,7]
target = 2
Initially the element at middle index is 4 which is greater than 2. Therefore we search the left half of the
array i.e. [1,2,3].
Here we find the middle element equal to target element so we return its index i.e. 1
target = 9
A simple Binary Search implementation may return -1 as 9 is not present in the array. A more complex one would return the index at which 9 would have to be inserted, which would be `-8` (last position in the array (7) plus one (7+1), negated)`.
A CS50 video explaining the Binary Search Algorithm