int binarySearch(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;

    while (left <= right) {
        int mid = left + (right - left)/2;
        if (nums[mid] == target){
            return mid;
        }
        else if (nums[mid] < target){
            left = mid + 1;
        }
        else if (nums[mid] > target){
            right = mid - 1;
        }
    }

    return -1;
}

Midpoint

• C++ drops the decimal in division
  • $5/2 \rightarrow 2$
  • $-5/2\rightarrow-2$
• The above algorithm picks
  • The exact middle or,
  • If there are two middles, picks the left one
• Another performant way to calculate the midpoint to avoid integer overflow
  • pivot = ((unsigned int)left + (unsigned int)right) >> 1;

Where left lands when the loop ends

• The loop exits when left > right, i.e. the pointers cross
• At that moment:
  • right sits just left of where target belongs
  • left sits just right of where target belongs
• So left is always the insert position

Reversing the search direction

• The == case is not special. What matters is which branch you push into
• Whatever condition sends you right (left = mid + 1) decides what left converges to

• Folding == into the < branch gives lower bound
• Folding == into the > branch gives upper bound
• This is what handles duplicates for free. No dedup needed
• If nothing qualifies, left lands at size(). % size() wraps it back to 0

Comparing characters in C++

• "a" < "c" compares pointers, not characters. Meaningless
• 'a' < 'c' compares ASCII values. Works