Skip to main content

Searching ✔

  1. The data structure (array/list) must be sorted.
  2. The elements must allow random access (so binary search works well with arrays, but not linked lists without modifications).

Why Binary Search is Not Efficient on Linked List​

  • In a linked list, accessing the middle element requires traversing nodes from the head → O(n).
  • Binary Search depends on direct middle access (O(1) in arrays).
  • Hence, overall complexity in linked lists becomes O(nlogn), worse than a simple linear search O(n).
  • Special cases: binary search can still be implemented using fast and slow pointers, Use slow and fast pointers to find middle node. Then recurse/search left or right half. But it’s rarely used in practice.
  • Time Complexity:
    • Best case: O(1) (element found at first mid).
    • Worst/Average: O(logn).
danger
  • Space Complexity:
    • Iterative: O(1).
    • Recursive: O(logn) (stack calls).

Lower Bound​

The lower bound of a target value is the first position in a sorted array where the element is greater than or equal to the target.

  • If the target exists → it gives the first index of that target.
danger
  • If the target doesn’t exist → it gives the index where the element could be inserted while keeping the array sorted
  • Example: In [1, 2, 4, 4, 5], lower bound of 4 = index 2.
  • Useful in searching with duplicates.

Upper Bound​

The upper bound of a target value is the first position in a sorted array where the element is greater than the target.

  • If the target exists multiple times → it gives the index of the element just after the last occurrence.
danger
  • If the target doesn’t exist → it gives the index where an element greater than target could be inserted.
  • Example: In [1, 2, 4, 4, 5], upper bound of 4 = index 4.
  • Used in range queries, frequency count.

Binary Search on 2D Arrays​

danger
  • If matrix is row-wise & column-wise sorted, binary search can be applied:
    • Flatten 2D into 1D index.
    • Or do stepwise search (start from top-right or bottom-left).
  • Example: searching element in a matrix efficiently in O(log(m×n)).

Search in Infinite/Unknown Size Arrays​

  • When array size is not known (like an infinite stream).
  • Technique:
    1. Start with bound = 1.
    2. Double bound (2, 4, 8, …) until arr[bound] >= target.
    3. Apply binary search within last known range.
  • Used in problems like searching in online data streams.

Implementation Comparison​

  • Implmentation of lower bound and upper bound is as same as Lower Bound, just modify the condition
  • If target exists in the array:
danger
  • First Occrrence = Lower Bound
  • Last Occurrence = Upper Bound - 1
  • Ceil = Floor = arr[lower_bound]
0  1 2 3  4 5
-------------
1 [2 2 2] 3 4 - target = 2
  ^       ^
  lb      ub

  • First Occurrence = lower_bound = 1

  • Last Occurrence = upper_bound - 1 = 3

  • Ceil = Floor = arr[lower_bound] = 2

  • If target doesn't exists in the array:

danger
  • lower_bound = upper_bound
  • First Occurrence = -1
  • Last Occurrence = -1
  • Ceil = arr[lower_bound]
  • Floor = arr[lower_bound - 1]
1 2 |4 4 5 - target = 3
      ^
   lb = ub = 2
  • First Occurrence = -1
  • Last Occurrence = -1
  • Ceil = arr[lower_bound] = 4
  • Floor = arr[lower_bound - 1] = arr[1] = 2