Interview Revision

Binary Search Patterns for DSA Revision

Overview: Binary Search applies to sorted or monotonic data:. It repeatedly halves the search space to locate a target or threshold efficiently (O(log N)). Key patterns:
  • Direct Search / Bound Queries: Search target, find insert position, lower/upper bound (first ≥/first > target)::.
  • Range/Count Queries: Locate first/last occurrence of a value, count ≤ X, etc.::.
  • Search in Rotated Array: Use modified binary search by identifying sorted halves:.
  • Binary Search on Answer: Optimize a parameter by defining a monotonic feasibility predicate::.
Below are patterns covering these cases, with example problems and solutions in Java.

Works when the array is sorted. Typical tasks include searching for a target, inserting into a sorted array, and finding floor/ceil values. Key variants:
  • Standard Search: Binary search for a target in *O*(log N) time:.
  • Lower/Upper Bound: Find the first index where element ≥ target (lower bound) or > target (upper bound)::.
  • First/Last Occurrence: Use binary search to find first or last position of a value (e.g., first and last index of a value):.
  • Insert Position: Equivalent to lower bound; find where to insert target to maintain sorted order:.
  • Floor/Ceil: Floor is the largest element ≤ target (basically one less than a lower bound); Ceil is the smallest ≥ target (a lower bound):.
Logic: At each step compare arr[mid] with target. Move left or right accordingly. Stop when pointers cross.

Example Problems:

Search an element in sorted arrayFind first and last occurrence of a value

Solution Spotlight: Search an element in sorted array

We maintain two pointers left and right. Compute mid = (left+right)/2:
  • If arr[mid] equals the target, the element is found.
  • If arr[mid] is less than target, search the right half (left = mid + 1).
  • Otherwise search the left half (right = mid - 1).
Continue until left > right (target not found).
Dry Run: For arr = [2,5,6,8] and target = 6: initially left=0, right=3.
  • mid=1 → arr[1]=5 < 6, so set left=2.
  • Now left=2, right=3, mid=2 → arr[2]=6 == target, return index 2.
Complexity: O(log N) time.

Searchanelementinsortedarray.java

Loading code syntax...