🔍 Binary Search

[tpemeja]

Summary

• Patterns

  • Basic Binary Search: find exact element in sorted data; O(log n).
  • Lower/Upper Bound: first index with a[i] ≥ x or > x; range counting/placement; O(log n).
  • Search in Rotated Array: leverage one-sorted-half invariant; O(log n) (may degrade with duplicates).
  • Binary Search on Answer: search minimal/maximal feasible value via monotone predicate; O(log R · check).

• Choose

  • Exact match in sorted array → Basic Binary Search
  • First/last occurrence, count equals, insertion point → Lower/Upper Bound
  • Sorted but rotated array (maybe with duplicates) → Rotated Binary Search
  • Optimize minimal/maximal value satisfying constraint → Binary Search on Answer

Details

✅ Basic Binary Search

Summary (Key points):

• Maintain an invariant over a sorted range; halve the search space each step.
• Two common loops:
  • l ≤ r for exact index (returns -1 if not found).
  • l < r for first-true/last-false style.
• Use mid = l + (r − l) // 2; update l = mid + 1 or r = mid − 1 to avoid infinite loops.

Details

• Concept recap:

  • For exact search on sorted array a: compare a[mid] with target; move left/right accordingly.
  • For functions over integers (monotone), use “first true” template (see Binary Search on Answer).

• Generic template (exact index or -1):

  def binary_search(a, target):
      l, r = 0, len(a) - 1
      while l <= r:
          m = (l + r) // 2
          if a[m] == target:
              return m
          if a[m] < target:
              l = m + 1
          else:
              r = m - 1
      return -1

• Case 1: Binary Search

  • Exact index in sorted array or -1 if absent.
  • Time: O(log n), Space: O(1).

  def search(nums, target):
      l, r = 0, len(nums) - 1
      while l <= r:
          m = (l + r) // 2
          if nums[m] == target:
              return m
          if nums[m] < target:
              l = m + 1
          else:
              r = m - 1
      return -1

• Case 2: Sqrt(x)

  • Largest m with m*m ≤ x (integer floor).
  • Time: O(log x), Space: O(1).

  def mySqrt(x: int) -> int:
      l, r = 0, x
      ans = 0
      while l <= r:
          m = (l + r) // 2
          if m * m <= x:
              ans = m
              l = m + 1
          else:
              r = m - 1
      return ans

• Case 3: First Bad Version

  • First index where isBadVersion(i) is True.
  • Time: O(log n), Space: O(1).

  # isBadVersion is given
  def firstBadVersion(n: int) -> int:
      l, r = 1, n
      while l < r:
          m = (l + r) // 2
          if isBadVersion(m):
              r = m
          else:
              l = m + 1
      return l

• Case 4: Valid Perfect Square

  • Check if x is a perfect square via search on m.
  • Time: O(log x), Space: O(1).

  def isPerfectSquare(x: int) -> bool:
      if x < 2:
          return True
      l, r = 1, x // 2
      while l <= r:
          m = (l + r) // 2
          mm = m * m
          if mm == x:
              return True
          if mm < x:
              l = m + 1
          else:
              r = m - 1
      return False

• Pitfalls and tips:

  • Ensure movement: when a[m] < target, do l = m + 1; when >, r = m − 1.
  • For huge numbers (non-Python), beware overflow in m*m.
  • Prefer integer domain and pure comparisons; avoid floating errors.

• Complexity summary:

  • O(log n) time, O(1) extra space.

✅ Lower / Upper Bound

Summary (Key points):

• lower_bound: first index i with a[i] ≥ x.
• upper_bound: first index i with a[i] > x.
• Use half-open interval [l, r) with invariant: answer ∈ [l, r).
• Great for counts, insertion points, first/last occurrence.

Details

• Generic templates:

  def lower_bound(a, x):
      l, r = 0, len(a)
      while l < r:
          m = (l + r) // 2
          if a[m] < x:
              l = m + 1
          else:
              r = m
      return l  # first i with a[i] >= x
  
  def upper_bound(a, x):
      l, r = 0, len(a)
      while l < r:
          m = (l + r) // 2
          if a[m] <= x:
              l = m + 1
          else:
              r = m
      return l  # first i with a[i] > x

• Case 1: Find First and Last Position of Element in Sorted Array

  • Use lb = lower_bound(a, x), ub = upper_bound(a, x) − 1; check bounds.
  • Time: O(log n), Space: O(1).

  def searchRange(nums, target):
      def lb(a, x):
          l, r = 0, len(a)
          while l < r:
              m = (l + r) // 2
              if a[m] < x: l = m + 1
              else: r = m
          return l
      def ub(a, x):
          l, r = 0, len(a)
          while l < r:
              m = (l + r) // 2
              if a[m] <= x: l = m + 1
              else: r = m
          return l
      l = lb(nums, target)
      r = ub(nums, target) - 1
      if l <= r and 0 <= l < len(nums) and nums[l] == target and nums[r] == target:
          return [l, r]
      return [-1, -1]

• Case 2: Successful Pairs of Spells and Potions

  • Sort potions; for each spell s, need potions[j] ≥ ceil(success / s).
  • Time: O(n log n + m log n), Space: O(1) extra aside from sorting.

  import math
  def successfulPairs(spells, potions, success):
      potions.sort()
      res = []
      n = len(potions)
      for s in spells:
          need = (success + s - 1) // s  # ceil(success / s)
          l, r = 0, n
          while l < r:
              m = (l + r) // 2
              if potions[m] < need:
                  l = m + 1
              else:
                  r = m
          res.append(n - l)
      return res

• Case 3: Find Smallest Letter Greater Than Target

  • upper_bound with wrap-around if ub == n.
  • Time: O(log n), Space: O(1).

  def nextGreatestLetter(letters, target):
      l, r = 0, len(letters)
      while l < r:
          m = (l + r) // 2
          if letters[m] <= target:
              l = m + 1
          else:
              r = m
      return letters[0] if l == len(letters) else letters[l]

• Case 4 (bonus technique): Longest Increasing Subsequence via patience sorting

  • tails array uses lower_bound to place each x.
  • Time: O(n log n), Space: O(n).

  import bisect
  def lengthOfLIS(nums):
      tails = []
      for x in nums:
          i = bisect.bisect_left(tails, x)
          if i == len(tails):
              tails.append(x)
          else:
              tails[i] = x
      return len(tails)

• Pitfalls and tips:

  • For duplicates, lower_bound gives first occurrence, upper_bound gives index after last.
  • Use half-open [l, r) to avoid off-by-one; return l as insertion point.
  • Check bounds before indexing with returned positions.

• Complexity summary:

  • Each bound query O(log n); total depends on number of queries/sorts.

✅ Search in Rotated Array

Summary (Key points):

• One half is always sorted (without duplicates); decide which half to discard.
• With duplicates, equal ends can break the invariant; shrink edges linearly.
• Works in O(log n) typically; with heavy duplicates, worst-case O(n).

Details

• Template (no duplicates, strictly increasing before rotation):

  def search_rotated(nums, target):
      l, r = 0, len(nums) - 1
      while l <= r:
          m = (l + r) // 2
          if nums[m] == target:
              return m
          # Left half sorted
          if nums[l] <= nums[m]:
              if nums[l] <= target < nums[m]:
                  r = m - 1
              else:
                  l = m + 1
          # Right half sorted
          else:
              if nums[m] < target <= nums[r]:
                  l = m + 1
              else:
                  r = m - 1
      return -1

• Case 1: Search in Rotated Sorted Array

  • Use the above template (no duplicates).
  • Time: O(log n), Space: O(1).

• Case 2: Search in Rotated Sorted Array II

  • With duplicates: when nums[l] == nums[m] == nums[r], shrink edges.
  • Time: Average O(log n), Worst O(n), Space: O(1).

  def search(nums, target):
      l, r = 0, len(nums) - 1
      while l <= r:
          m = (l + r) // 2
          if nums[m] == target:
              return True
          if nums[l] == nums[m] == nums[r]:
              l += 1
              r -= 1
              continue
          if nums[l] <= nums[m]:
              if nums[l] <= target < nums[m]:
                  r = m - 1
              else:
                  l = m + 1
          else:
              if nums[m] < target <= nums[r]:
                  l = m + 1
              else:
                  r = m - 1
      return False

• Pitfalls and tips:

  • Beware equal boundaries; only the m == l == r case forces linear shrink.
  • Alternative: find pivot (min index) first, then do classic binary search in the correct half.

• Complexity summary:

  • O(log n) without duplicates; O(n) worst-case with duplicates.

✅ Binary Search on Answer

Summary (Key points):

• Search over the space of answers, not indices.
• Define a monotone predicate f(x): False...False, then True...True (or vice versa).
• Use first-true (min feasible) or last-false (max infeasible + 1).
• Ensure upper bound hi is feasible; widen by doubling if needed.

Details

• Generic template (first true in [lo, hi]):

  def first_true(lo, hi, pred):
      # Find minimal x in [lo, hi] such that pred(x) is True.
      while lo < hi:
          mid = (lo + hi) // 2
          if pred(mid):
              hi = mid
          else:
              lo = mid + 1
      return lo

• Case 1: Koko Eating Bananas

  • f(k): hours needed at speed k ≤ H.
  • Time: O(n log max(pile)), Space: O(1).

  import math
  def minEatingSpeed(piles, h):
      lo, hi = 1, max(piles)
      def ok(k):
          return sum((p + k - 1) // k for p in piles) <= h
      while lo < hi:
          mid = (lo + hi) // 2
          if ok(mid):
              hi = mid
          else:
              lo = mid + 1
      return lo

• Case 2: Capacity To Ship Packages Within D Days

  • f(C): simulate days with capacity C, check ≤ D.
  • Time: O(n log sum(weights)), Space: O(1).

  def shipWithinDays(weights, days):
      lo, hi = max(weights), sum(weights)
      def ok(cap):
          d = 1
          cur = 0
          for w in weights:
              if cur + w > cap:
                  d += 1
                  cur = 0
              cur += w
          return d <= days
      while lo < hi:
          mid = (lo + hi) // 2
          if ok(mid):
              hi = mid
          else:
              lo = mid + 1
      return lo

• Case 3: Find the Smallest Divisor Given a Threshold

  • f(d): sum(ceil(a_i / d)) ≤ threshold.
  • Time: O(n log max(nums)), Space: O(1).

  def smallestDivisor(nums, threshold):
      lo, hi = 1, max(nums)
      def ok(d):
          s = 0
          for x in nums:
              s += (x + d - 1) // d
              if s > threshold:
                  return False
          return True
      while lo < hi:
          mid = (lo + hi) // 2
          if ok(mid):
              hi = mid
          else:
              lo = mid + 1
      return lo

• Case 4: Minimum Time to Complete Trips

  • f(T): sum(T // t_i) ≥ totalTrips.
  • Time: O(n log (min(t)·totalTrips)), Space: O(1).

  def minimumTime(time, totalTrips):
      lo, hi = 1, min(time) * totalTrips
      def ok(T):
          trips = 0
          for t in time:
              trips += T // t
              if trips >= totalTrips:
                  return True
          return False
      while lo < hi:
          mid = (lo + hi) // 2
          if ok(mid):
              hi = mid
          else:
              lo = mid + 1
      return lo

• Case 5: Split Array Largest Sum

  • f(S): can split into ≤ m subarrays with each subarray sum ≤ S.
  • Time: O(n log sum(nums)), Space: O(1).

  def splitArray(nums, m):
      lo, hi = max(nums), sum(nums)
      def ok(S):
          parts = 1
          cur = 0
          for x in nums:
              if cur + x > S:
                  parts += 1
                  cur = 0
              cur += x
          return parts <= m
      while lo < hi:
          mid = (lo + hi) // 2
          if ok(mid):
              hi = mid
          else:
              lo = mid + 1
      return lo

• Pitfalls and tips:

  • Monotonicity: ensure pred(mid) flips exactly once; otherwise BS is invalid.
  • Bounds: choose lo/hi so that answer ∈ [lo, hi] and pred(hi) is True (for first-true).
  • Integer math: use integer ceilings via (x + d − 1) // d to avoid floats.
  • If unknown hi, grow by doubling until pred(hi) True.

• Complexity summary:

  • O(log R · check) where R is the answer range; check usually O(n).

[tpemeja]

https://www.geeksforgeeks.org/dsa/binary-search/

[tpemeja]

Lower Bound : first index i with a[i] ≥ x

If a[m] < x, move left up: l = m + 1
Else (a[m] ≥ x), shrink right to include m: r = m

Upper Bound : first index i with a[i] > x

If a[m] ≤ x, move left up: l = m + 1
Else (a[m] > x), shrink right to include m: r = m

[tpemeja]

Search in Rotated Array

No matter m, one side will be sorted just need to find which one to check if target is inside.

Find sorted side :

if A[m] >= A[l] :
=> Left shorted

https://learncodingfast.com/search-in-rotated-sorted-array/
else:
=> Right shorted

https://learncodingfast.com/search-in-rotated-sorted-array/

Check if target inside sorted section

If Left shorted

if A[l] <= target < A[m] :
=> Move right (r = m - 1) since checked A[m] != m before
else:
=> Move left (l = m + 1) since checked A[m] != m before

https://studyalgorithms.com/array/search-rotated-sorted-array/

If Right shorted

if A[m] < target <= A[r] :
=> Move left (l = m + 1) since checked A[m] != m before
else:
=> Move right (r = m - 1) since checked A[m] != m before

---

With duplicates :

• Shrink-left on tie (nums[l] == nums[m]): simplest and correct; can be slower on long duplicate tails. (If to decide which side is sorted using right then shrink-right)
• Triple-equal guard (nums[l] == nums[m] == nums[r]): shrink both ends to prune faster with heavy duplicates; worst-case still O(n).

[tpemeja]

Binary Search :

Ceiling division (ex: ceil(10,3) = 4 since need at least 4 time to be more than 10)

We add k−1 to p to do ceiling division with integers: hours per pile = ceil(p/k) = (p + k − 1) // k, since // is floor and you can’t use partial hours.
Alternatives: (p // k) + (p % k != 0) or -(-p // k) in Python; valid for non-negative integers.