#algorithm #search

idea

Binary search works on sorted arrays, in $O(log(n))$

  1. Begin with the middle.
  2. If value > search, search in right. Else search in left.
  3. Next index is middle of the segment. ($low+ \frac{high - low}{2}$)

function binary_search(A, n, T) is 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

reference

Reference implementation in C#

        public int Search(int[] nums, int target) {
        var left = 0;
        var right = nums.Length - 1;
        while (left <= right) {
            int pivot = (int)Math.Floor((Double)(left + right) / 2);
            if (nums[pivot] < target) {
                left = pivot + 1;
            } else if (nums[pivot] > target) {
                right = pivot - 1;
            } else {
                return pivot;
            }
        }
        return -1;
    }