##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
Binary search is a fast algorithm for finding a target value in a sorted array. Instead of checking every element like linear search at , you repeatedly split the search space in half.
Here's the key insight: if the array is sorted, one comparison tells you which half contains your target. You eliminate of remaining elements each step.
This halving gives you time complexity. For an array of million elements, you need at most comparisons instead of million.
Apply what you learned by solving the practice problem for Binary Search.
Go to Practice ProblemYou maintain two pointers: left and right, representing the current search range.
Calculate the middle index: mid = left + (right - left) / 2
Compare arr[mid] with your target:
right = mid - 1left = mid + 1 Repeat until left > right (target not found)
Visualize it as a decision tree. Each node is a comparison. You follow one branch and discard the other. The tree height is , so that's your worst-case comparisons.
Here's the classic binary search:
function binarySearch(arr, target):
left = 0
right = arr.length - 1
while left <= right:
mid = left + (right - left) / 2
if arr[mid] == target:
return mid
else if arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
I use left + (right - left) / 2 instead of (left + right) / 2 to prevent integer overflow when left and right are large.
The condition left <= right ensures you check single-element ranges. If you use left < right, you might miss the target when it's the only element left.
Off-by-one errors: Should you set right = mid or right = mid - 1? It depends on your loop condition. With left <= right, use mid - 1 and mid + 1 to avoid infinite loops.
Infinite loops: If left = mid when left + 1 == right, you loop forever. Always ensure your boundaries move.
Wrong return value: When the target doesn't exist, left points to where it would be inserted. This is useful for lower bound searches.
Debugging tip: Print left, right, and mid each iteration. Watch for boundaries that stop moving.
Lower bound (first occurrence): When you find the target, don't return immediately. Set right = mid - 1 and keep searching left. Return left at the end.
Upper bound (last occurrence): When you find the target, set left = mid + 1 and keep searching right. Return right at the end.
Binary search on answer: When asked to minimize or maximize a value, binary search the answer space. For each candidate, check if it's feasible. This works on any monotonic condition.
Complexity: All variants run in time with space. The search space halves each step regardless of the variant you use.