Binary Search

1// Classic binary search — sorted array, exact match
2int binarySearch(vector<int>& arr, int target)
3{
4    int lo = 0;
5    int hi = (int)arr.size() - 1;
6 
7    while (lo <= hi)
8    {
9        int mid = lo + (hi - lo) / 2;
10 
11        if (arr[mid] == target)
12        {
13            return mid;              // found
14        }
15        else if (arr[mid] < target)
16        {
17            lo = mid + 1;            // search right half
18        }
19        else
20        {
21            hi = mid - 1;            // search left half
22        }
23    }
24 
25    return -1;   // not found  (return lo for insertion index)
26}