idea
Binary search works on sorted arrays, in $O(log(n))$
- Begin with the middle.
- If value > search, search in right. Else search in left.
- 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;
}