Binary Search Visualizer

Binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item, until you've narrowed down the possible locations to just one.

The Algorithm Steps

1. Initialize Pointers: Start with two pointers, lo = 0 (the beginning of the array) and hi = array.length - 1 (the end).
2. Calculate Middle: Find the middle index: mid = lo + Math.floor((hi - lo) / 2). This specific formula prevents integer overflow that can occur in languages like Java or C++ if you simply do (lo + hi) / 2.
3. Compare: Compare the target value to the middle element, array[mid]:

• If array[mid] === target, you found the target!
• If array[mid] < target, the target must be in the right half. Update lo = mid + 1.
• If array[mid] > target, the target must be in the left half. Update hi = mid - 1.

4. Repeat: Continue this process while lo <= hi.
5. Not Found: If lo exceeds hi, the search range is empty, meaning the target is not in the array. Return -1.

Handling Duplicates

The standard algorithm returns as soon as it finds a match. To find the first or last occurrence of a duplicated value, the algorithm is slightly modified:

• First Occurrence: When array[mid] === target, record the index but continue searching the left half (hi = mid - 1) to see if an earlier duplicate exists.
• Last Occurrence: When array[mid] === target, record the index but continue searching the right half (lo = mid + 1) to find a later duplicate.

Complexity Analysis

• Time Complexity: $O(\log n)$ — Because the search space is halved with every step, the number of comparisons grows logarithmically. An array of 1,000,000 items takes at most ~20 comparisons!
• Space Complexity: $O(1)$ — The iterative version only requires a few variables to store pointers, requiring constant extra memory.