Binary search locates a value in a sorted array by repeatedly comparing it with the middle element and discarding the impossible half. Because each comparison narrows the range, it can find 18 in three comparisons instead of eight. section 13.2.1
The process is straightforward:
- Start with the complete index range. section 13.2.1
- Compare the target with the middle element. section 13.2.1
- Keep the upper or lower half according to the comparison, then repeat. section 13.2.1
Searching a sorted Julia array
A = [2, 7, 9, 10, 11, 12, 15, 18, 19]\nsearchsorted(A, 18) # 8:8\nsearchsortedfirst(A, 18) # 8\nsearchsortedlast(A, 18) # 8\n\nThe array must remain sorted. Insertions can therefore require re-sorting, unlike set operations designed for membership checks. section 13.2.1
