Skip to content

09. Binary Search#

Theory#

Binary search requires a monotonic predicate: once f(i) becomes true, it stays true (or the opposite for upper-bound variants). The array being sorted is the classic case — f(i) = (nums[i] >= target).

Three templates#

Goal Invariant Typical loop
Exact match lo <= hi return -1 if not found
Lower bound (first true) lo < hi, shrink hi mid = (lo+hi)//2; if pred(mid): hi=mid else lo=mid+1
Upper bound (last false) same as lower bound on negated pred return lo 
def lower_bound(nums, target):
    lo, hi = 0, len(nums)
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] >= target:
            hi = mid
        else:
            lo = mid + 1
    return lo

Binary search on the answer space#

When the problem asks to minimize the maximum or maximize the minimum, binary search the answer range, not the array:

  1. Identify monotonic feasibility: can(x) = "is answer x achievable?"
  2. Binary search the smallest/largest x where can(x) is true.

Examples: LC 875 (Koko eating bananas), LC 1011 (capacity to ship), LC 410 (split array largest sum).

Pitfalls#

  • Use mid = lo + (hi - lo) // 2 to avoid overflow (habit; Python ints are fine but interviewers notice).
  • Clarify inclusive vs exclusive hi — off-by-one bugs are the #1 failure mode.
  • Duplicates: lower bound finds first occurrence; upper bound finds insertion point after run.

See also: Searching.

Problems at a glance#

LC Problem
704 Binary Search ↗
35 Search Insert Position ↗
852 Peak Index in a Mountain Array ↗
34 Find First and Last Position of Element in Sorted Array ↗
875 Koko Eating Bananas ↗
410 Split Array Largest Sum ↗
1011 Capacity To Ship Packages Within D Days ↗
1283 Find the Smallest Divisor Given a Threshold ↗
33 Search in Rotated Sorted Array ↗
81 Search in Rotated Sorted Array II ↗
300 Longest Increasing Subsequence ↗
744 Find Smallest Letter Greater Than Target ↗
278 First Bad Version ↗
162 Find Peak Element ↗
69 Sqrt(x) ↗
74 Search a 2D Matrix ↗

Problem 1: Binary Search (Leetcode:704)#

Problem Statement

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

Example 2:

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1

Constraints:

  • 1 <= nums.length <= 104
  • -104 < nums[i], target < 104
  • All the integers in nums are unique.
  • nums is sorted in ascending order.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def search(self, nums: list[int], target: int) -> int:
        lo, hi = 0, len(nums) - 1
        while lo <= hi:
            mid = lo + (hi - lo) // 2
            if nums[mid] == target:
                return mid
            if nums[mid] < target:
                lo = mid + 1
            else:
                hi = mid - 1
        return -1
Explanation:

  1. Maintain a closed interval [lo, hi] that always contains the target if it exists.
  2. Compare nums[mid] to target and discard the half that cannot contain the answer.
  3. Stop when the interval is empty (lo > hi), returning -1.

Time: O(log n)  |  Space: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def search(self, nums: list[int], target: int) -> int:
        lo, hi = 0, len(nums)
        while lo < hi:
            mid = lo + (hi - lo) // 2
            if nums[mid] >= target:
                hi = mid
            else:
                lo = mid + 1
        return lo if lo < len(nums) and nums[lo] == target else -1
Explanation:

  1. Use the lower bound template: find the first index where nums[i] >= target.
  2. Half-open range [lo, hi) with hi = len(nums) avoids off-by-one when the target is larger than all elements.
  3. After the loop, check whether nums[lo] actually equals target.

Time: O(log n)  |  Space: O(1)

Problem 2: Search Insert Position (Leetcode:35)#

Problem Statement

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [1,3,5,6], target = 5
Output: 2

Example 2:

Input: nums = [1,3,5,6], target = 2
Output: 1

Example 3:

Input: nums = [1,3,5,6], target = 7
Output: 4

Constraints:

  • 1 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • nums contains distinct values sorted in ascending order.
  • -104 <= target <= 104
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def searchInsert(self, nums: list[int], target: int) -> int:
        lo, hi = 0, len(nums)
        while lo < hi:
            mid = lo + (hi - lo) // 2
            if nums[mid] >= target:
                hi = mid
            else:
                lo = mid + 1
        return lo
Explanation:

  1. The answer is exactly the lower bound of target: the first index where nums[i] >= target.
  2. If target is present, that index is its position; otherwise it is the insertion point.
  3. No extra check is needed because lo is always a valid insertion index in [0, len(nums)].

Time: O(log n)  |  Space: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def searchInsert(self, nums: list[int], target: int) -> int:
        lo, hi = 0, len(nums) - 1
        while lo <= hi:
            mid = lo + (hi - lo) // 2
            if nums[mid] == target:
                return mid
            if nums[mid] < target:
                lo = mid + 1
            else:
                hi = mid - 1
        return lo
Explanation:

  1. Standard exact-match binary search; when the loop ends without a match, lo points to the insertion index.
  2. Example: target = 2 in [1,3,5,6] — after discarding smaller values, lo stops at index 1.
  3. Equivalent to lower bound but written with the inclusive [lo, hi] template.

Time: O(log n)  |  Space: O(1)

Problem 3: Peak Index in a Mountain Array (Leetcode:852)#

Problem Statement

You are given an integer mountain array arr of length n where the values increase to a peak element and then decrease.

Return the index of the peak element.

Your task is to solve it in O(log(n)) time complexity.

Example 1:

Input: arr = [0,1,0]
Output: 1

Example 2:

Input: arr = [0,2,1,0]
Output: 1

Example 3:

Input: arr = [0,10,5,2]
Output: 1

Constraints:

  • 3 <= arr.length <= 105
  • 0 <= arr[i] <= 106
  • arr is guaranteed to be a mountain array.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def peakIndexInMountainArray(self, arr: list[int]) -> int:
        lo, hi = 0, len(arr) - 1
        while lo < hi:
            mid = lo + (hi - lo) // 2
            if arr[mid] < arr[mid + 1]:
                lo = mid + 1      # still ascending
            else:
                hi = mid          # at or past the peak
        return lo
Explanation:

  1. Compare arr[mid] with arr[mid + 1] to detect whether we are on the ascending or descending side.
  2. If ascending (arr[mid] < arr[mid + 1]), the peak is at or to the right — move lo = mid + 1.
  3. Otherwise the peak is at mid or to the left — shrink with hi = mid.
  4. Invariant: the peak index is always in [lo, hi].

Time: O(log n)  |  Space: O(1)

1
2
3
4
5
6
class Solution:
    def peakIndexInMountainArray(self, arr: list[int]) -> int:
        for i in range(len(arr) - 1):
            if arr[i] > arr[i + 1]:
                return i
        return len(arr) - 1
Explanation:

  1. Walk left to right until the first index where the next value is smaller — that index is the peak.
  2. Correct but O(n); included to contrast with the logarithmic binary search approach.
  3. Useful when the array is tiny or as a sanity check while learning the BS variant.

Time: O(n)  |  Space: O(1)

2. First / Last Occurrence#

Problem 1: Find First and Last Position of Element in Sorted Array (Leetcode:34)#

Problem Statement

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

Example 3:

Input: nums = [], target = 0
Output: [-1,-1]

Constraints:

  • 0 <= nums.length <= 105
  • -109 <= nums[i] <= 109
  • nums is a non-decreasing array.
  • -109 <= target <= 109
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def searchRange(self, nums: list[int], target: int) -> list[int]:
        def lower_bound(x: int) -> int:
            lo, hi = 0, len(nums)
            while lo < hi:
                mid = lo + (hi - lo) // 2
                if nums[mid] >= x:
                    hi = mid
                else:
                    lo = mid + 1
            return lo

        def upper_bound(x: int) -> int:
            lo, hi = 0, len(nums)
            while lo < hi:
                mid = lo + (hi - lo) // 2
                if nums[mid] > x:
                    hi = mid
                else:
                    lo = mid + 1
            return lo

        first = lower_bound(target)
        if first == len(nums) or nums[first] != target:
            return [-1, -1]
        return [first, upper_bound(target) - 1]
Explanation:

  1. Lower bound finds the first index with nums[i] >= target; verify it equals target.
  2. Upper bound finds the first index with nums[i] > target; the last occurrence is one before that.
  3. Two O(log n) searches handle duplicate runs without scanning the whole array.

Time: O(log n)  |  Space: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def searchRange(self, nums: list[int], target: int) -> list[int]:
        lo, hi = 0, len(nums) - 1
        idx = -1
        while lo <= hi:
            mid = lo + (hi - lo) // 2
            if nums[mid] == target:
                idx = mid
                break
            if nums[mid] < target:
                lo = mid + 1
            else:
                hi = mid - 1
        if idx == -1:
            return [-1, -1]

        left = right = idx
        while left > 0 and nums[left - 1] == target:
            left -= 1
        while right + 1 < len(nums) and nums[right + 1] == target:
            right += 1
        return [left, right]
Explanation:

  1. Binary search finds any occurrence of target in O(log n).
  2. Expand left and right while neighbors still equal target.
  3. Worst case O(n) when all elements are target, but simple when duplicate runs are short.

Time: O(log n) best, O(n) worst  |  Space: O(1)

Problem 2: Count Occurrences of a Number in a Sorted Array (GeeksforGeeks)#

Problem Statement

Given a sorted array arr[] and a number x, find the number of occurrences of x in arr[].

Example 1:

Input: arr = [1, 1, 1, 2, 3, 3, 3, 3], x = 3
Output: 4

Example 2:

Input: arr = [5, 7, 7, 8, 8, 10], x = 7
Output: 2

Example 3:

Input: arr = [1, 2, 4, 4, 4, 4, 7, 9], x = 4
Output: 4

Constraints:

  • 1 <= arr.length <= 105
  • arr is sorted in non-decreasing order
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def count_occurrences(arr: list[int], x: int) -> int:
    def lower_bound(val: int) -> int:
        lo, hi = 0, len(arr)
        while lo < hi:
            mid = lo + (hi - lo) // 2
            if arr[mid] >= val:
                hi = mid
            else:
                lo = mid + 1
        return lo

    def upper_bound(val: int) -> int:
        lo, hi = 0, len(arr)
        while lo < hi:
            mid = lo + (hi - lo) // 2
            if arr[mid] > val:
                hi = mid
            else:
                lo = mid + 1
        return lo

    first = lower_bound(x)
    if first == len(arr) or arr[first] != x:
        return 0
    return upper_bound(x) - first
Explanation:

  1. Count equals the length of the duplicate run: upper_bound(x) - lower_bound(x).
  2. Lower bound gives the first index; upper bound gives the insertion point after the last x.
  3. Handles absent elements by checking arr[first] != x.

Time: O(log n)  |  Space: O(1)

1
2
3
4
5
6
7
8
def count_occurrences(arr: list[int], x: int) -> int:
    count = 0
    for num in arr:
        if num == x:
            count += 1
        elif num > x:
            break
    return count
Explanation:

  1. Because the array is sorted, equal elements form a contiguous block.
  2. Count matches while scanning; stop early once num > x.
  3. O(n) but easy to reason about; binary search wins on large arrays with long duplicate runs.

Time: O(n)  |  Space: O(1)

3. Binary Search on Answer (Search Space)#

Problem 1: Koko Eating Bananas (Leetcode:875)#

Problem Statement

Koko loves to eat bananas. There are n piles of bananas, the ith pile has piles[i] bananas. The guards have gone and will come back in h hours.

Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour.

Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return.

Return the minimum integer k such that she can eat all the bananas within h hours.

Example 1:

Input: piles = [3,6,7,11], h = 8
Output: 4

Example 2:

Input: piles = [30,11,23,4,20], h = 5
Output: 30

Example 3:

Input: piles = [30,11,23,4,20], h = 6
Output: 23

Constraints:

  • 1 <= piles.length <= 104
  • piles.length <= h <= 109
  • 1 <= piles[i] <= 109
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
import math

class Solution:
    def minEatingSpeed(self, piles: list[int], h: int) -> int:
        def hours_needed(speed: int) -> int:
            return sum(math.ceil(pile / speed) for pile in piles)

        lo, hi = 1, max(piles)
        while lo < hi:
            mid = lo + (hi - lo) // 2
            if hours_needed(mid) <= h:
                hi = mid
            else:
                lo = mid + 1
        return lo
Explanation:

  1. Predicate: can(k) = (total hours at speed k <= h). Faster speed makes this easier — monotonic.
  2. Search the minimum feasible k in [1, max(piles)].
  3. Validation scans all piles once per BS step: O(n log max(piles)).

Time: O(n log max(piles))  |  Space: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
import math

class Solution:
    def minEatingSpeed(self, piles: list[int], h: int) -> int:
        def hours_needed(speed: int) -> int:
            return sum(math.ceil(pile / speed) for pile in piles)

        for speed in range(1, max(piles) + 1):
            if hours_needed(speed) <= h:
                return speed
        return max(piles)
Explanation:

  1. Try every speed from 1 upward until one finishes within h hours.
  2. Same validation function as Approach 1, but no binary search on the answer range.
  3. Correct but O(n · max(piles)) — shows why BS on the answer space matters.

Time: O(n · max(piles))  |  Space: O(1)

Problem 2: Split Array Largest Sum (Leetcode:410)#

Problem Statement

Given an integer array nums and an integer k, split nums into k non-empty subarrays such that the largest sum of any subarray is minimized.

Return the minimized largest sum of the split.

A subarray is a contiguous part of the array.

Example 1:

Input: nums = [7,2,5,10,8], k = 2
Output: 18
Explanation: There are four ways to split nums into two subarrays.
The best way is to split it into [7,2,5] and [10,8], where the largest sum among the two subarrays is only 18.

Example 2:

Input: nums = [1,2,3,4,5], k = 2
Output: 9
Explanation: There are four ways to split nums into two subarrays.
The best way is to split it into [1,2,3] and [4,5], where the largest sum among the two subarrays is only 9.

Constraints:

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 106
  • 1 <= k <= min(50, nums.length)
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def splitArray(self, nums: list[int], k: int) -> int:
        def can_split(limit: int) -> bool:
            parts = 1
            current = 0
            for num in nums:
                if current + num > limit:
                    parts += 1
                    current = num
                    if parts > k:
                        return False
                else:
                    current += num
            return True

        lo, hi = max(nums), sum(nums)
        while lo < hi:
            mid = lo + (hi - lo) // 2
            if can_split(mid):
                hi = mid
            else:
                lo = mid + 1
        return lo
Explanation:

  1. Binary search the answer: minimum largest subarray sum in [max(nums), sum(nums)].
  2. can_split(limit) greedily packs elements until adding the next would exceed limit, then starts a new part.
  3. If we need more than k parts, limit is too small.

Time: O(n log sum(nums))  |  Space: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def splitArray(self, nums: list[int], k: int) -> int:
        def can_split(limit: int) -> bool:
            parts = 1
            current = 0
            for num in nums:
                if current + num > limit:
                    parts += 1
                    current = num
                    if parts > k:
                        return False
                else:
                    current += num
            return True

        for limit in range(max(nums), sum(nums) + 1):
            if can_split(limit):
                return limit
        return sum(nums)
Explanation:

  1. Same greedy validator, but try every candidate limit from smallest to largest.
  2. First feasible limit is the answer because the predicate is monotonic.
  3. O(n · sum(nums)) — impractical for large sums; BS reduces the search to logarithmic steps.

Time: O(n · sum(nums))  |  Space: O(1)

Problem 3: Capacity To Ship Packages Within D Days (Leetcode:1011)#

Problem Statement

A conveyor belt has packages that must be shipped from one port to another within days days.

The ith package on the conveyor belt has a weight of weights[i]. Each day, we load the ship with packages on the conveyor belt (in the order given by weights). We may not load more weight than the maximum weight capacity of the ship.

Return the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within days days.

Example 1:

Input: weights = [1,2,3,4,5,6,7,8,9,10], days = 5
Output: 15
Explanation: A ship capacity of 15 is the minimum to ship all the packages in 5 days like this:
1st day: 1, 2, 3, 4, 5
2nd day: 6, 7
3rd day: 8
4th day: 9
5th day: 10

Note that the cargo must be shipped in the order given, so using a ship of capacity 14 and splitting the packages into parts like (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) is not allowed.

Example 2:

Input: weights = [3,2,2,4,1,4], days = 3
Output: 6
Explanation: A ship capacity of 6 is the minimum to ship all the packages in 3 days like this:
1st day: 3, 2
2nd day: 2, 4
3rd day: 1, 4

Example 3:

Input: weights = [1,2,3,1,1], days = 4
Output: 3
Explanation:
1st day: 1
2nd day: 2
3rd day: 3
4th day: 1, 1

Constraints:

  • 1 <= days <= weights.length <= 5 * 104
  • 1 <= weights[i] <= 500
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def shipWithinDays(self, weights: list[int], days: int) -> int:
        def can_ship(capacity: int) -> bool:
            needed_days = 1
            load = 0
            for w in weights:
                if load + w > capacity:
                    needed_days += 1
                    load = w
                    if needed_days > days:
                        return False
                else:
                    load += w
            return True

        lo, hi = max(weights), sum(weights)
        while lo < hi:
            mid = lo + (hi - lo) // 2
            if can_ship(mid):
                hi = mid
            else:
                lo = mid + 1
        return lo
Explanation:

  1. Search minimum capacity in [max(weights), sum(weights)].
  2. Greedy validation: pack packages in order until capacity is exceeded, then start a new day.
  3. Identical structure to LC 410 — minimize the maximum load subject to a partition count.

Time: O(n log sum(weights))  |  Space: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def shipWithinDays(self, weights: list[int], days: int) -> int:
        def can_ship(capacity: int) -> bool:
            needed_days = 1
            load = 0
            for w in weights:
                if load + w > capacity:
                    needed_days += 1
                    load = w
                    if needed_days > days:
                        return False
                else:
                    load += w
            return True

        for capacity in range(max(weights), sum(weights) + 1):
            if can_ship(capacity):
                return capacity
        return sum(weights)
Explanation:

  1. Try every capacity starting from the heaviest single package.
  2. First capacity that fits within days is optimal because more capacity only helps.
  3. Linear scan over the answer range; BS replaces this with O(log sum) steps.

Time: O(n · sum(weights))  |  Space: O(1)

Problem 4: Find the Smallest Divisor Given a Threshold (Leetcode:1283)#

Problem Statement

Given an array of integers nums and an integer threshold, we will choose a positive integer divisor, divide all the array by it, and sum the division's result. Find the smallest divisor such that the result mentioned above is less than or equal to threshold.

Each result of the division is rounded to the nearest integer greater than or equal to that element. (For example: 7/3 = 3 and 10/2 = 5).

The test cases are generated so that there will be an answer.

Example 1:

Input: nums = [1,2,5,9], threshold = 6
Output: 5
Explanation: We can get a sum to 17 (1+2+5+9) if the divisor is 1.
If the divisor is 4 we can get a sum of 7 (1+1+2+3) and if the divisor is 5 the sum will be 5 (1+1+1+2).

Example 2:

Input: nums = [44,22,33,11,1], threshold = 5
Output: 44

Constraints:

  • 1 <= nums.length <= 5 * 104
  • 1 <= nums[i] <= 106
  • nums.length <= threshold <= 106
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
import math

class Solution:
    def smallestDivisor(self, nums: list[int], threshold: int) -> int:
        def sum_after_divide(d: int) -> int:
            return sum(math.ceil(num / d) for num in nums)

        lo, hi = 1, max(nums)
        while lo < hi:
            mid = lo + (hi - lo) // 2
            if sum_after_divide(mid) <= threshold:
                hi = mid
            else:
                lo = mid + 1
        return lo
Explanation:

  1. Larger divisor → smaller ceiling-sum → easier to meet threshold. Search minimum feasible divisor.
  2. Upper bound max(nums) works because dividing by it gives sum n <= threshold (guaranteed by problem).
  3. Validation is a linear scan computing ceil(num / d) for each element.

Time: O(n log max(nums))  |  Space: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
import math

class Solution:
    def smallestDivisor(self, nums: list[int], threshold: int) -> int:
        def sum_after_divide(d: int) -> int:
            return sum(math.ceil(num / d) for num in nums)

        for d in range(1, max(nums) + 1):
            if sum_after_divide(d) <= threshold:
                return d
        return max(nums)
Explanation:

  1. Try divisors 1, 2, 3, … until the ceiling-sum drops to threshold or below.
  2. Same validation as Approach 1 without binary search on the answer.
  3. O(n · max(nums)) — acceptable only when values are small.

Time: O(n · max(nums))  |  Space: O(1)

4. Binary Search in Rotated Sorted Array#

Problem 1: Search in Rotated Sorted Array (Leetcode:33)#

Problem Statement

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly left rotated at an unknown index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be left rotated by 3 indices and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in `nums*.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Example 3:

Input: nums = [1], target = 0
Output: -1

Constraints:

  • 1 <= nums.length <= 5000
  • -104 <= nums[i] <= 104
  • All values of nums are unique.
  • nums is an ascending array that is possibly rotated.
  • -104 <= target <= 104
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def search(self, nums: list[int], target: int) -> int:
        lo, hi = 0, len(nums) - 1
        while lo <= hi:
            mid = lo + (hi - lo) // 2
            if nums[mid] == target:
                return mid

            if nums[lo] <= nums[mid]:          # left half is sorted
                if nums[lo] <= target < nums[mid]:
                    hi = mid - 1
                else:
                    lo = mid + 1
            else:                              # right half is sorted
                if nums[mid] < target <= nums[hi]:
                    lo = mid + 1
                else:
                    hi = mid - 1
        return -1
Explanation:

  1. At each step, one half of [lo, hi] is a normal sorted segment.
  2. Check whether target lies in the sorted half; if yes, search there, else discard that half.
  3. nums[lo] <= nums[mid] identifies which side is sorted (use <= because lo == mid is possible).

Time: O(log n)  |  Space: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def search(self, nums: list[int], target: int) -> int:
        def find_pivot() -> int:
            lo, hi = 0, len(nums) - 1
            while lo < hi:
                mid = lo + (hi - lo) // 2
                if nums[mid] > nums[hi]:
                    lo = mid + 1
                else:
                    hi = mid
            return lo

        def binary_search(left: int, right: int) -> int:
            lo, hi = left, right
            while lo <= hi:
                mid = lo + (hi - lo) // 2
                if nums[mid] == target:
                    return mid
                if nums[mid] < target:
                    lo = mid + 1
                else:
                    hi = mid - 1
            return -1

        pivot = find_pivot()
        if target >= nums[pivot] and target <= nums[-1]:
            return binary_search(pivot, len(nums) - 1)
        return binary_search(0, pivot - 1)
Explanation:

  1. Phase 1: find the rotation pivot (minimum element) with binary search.
  2. Phase 2: decide which sorted segment contains target, then run classic binary search there.
  3. Still O(log n) but two passes; Approach 1 is more compact for interviews.

Time: O(log n)  |  Space: O(1)

Problem 2: Search in Rotated Sorted Array II (Leetcode:81)#

Problem Statement

There is an integer array nums sorted in non-decreasing order (not necessarily with distinct values).

Before being passed to your function, nums is rotated at an unknown pivot index k (0 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,4,4,5,6,6,7] might be rotated at pivot index 5 and become [4,5,6,6,7,0,1,2,4,4].

Given the array nums after the rotation and an integer target, return true if target is in nums, or false if it is not in nums.

You must decrease the overall operation steps as much as possible.

Example 1:

Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true

Example 2:

Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false

Constraints:

  • 1 <= nums.length <= 5000
  • -104 <= nums[i] <= 104
  • nums is guaranteed to be rotated at some pivot.
  • -104 <= target <= 104

Follow up: This problem is similar to Search in Rotated Sorted Array, but nums may contain duplicates. Would this affect the runtime complexity? How and why?

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def search(self, nums: list[int], target: int) -> bool:
        lo, hi = 0, len(nums) - 1
        while lo <= hi:
            mid = lo + (hi - lo) // 2
            if nums[mid] == target:
                return True

            if nums[lo] == nums[mid] == nums[hi]:
                lo += 1
                hi -= 1
                continue

            if nums[lo] <= nums[mid]:
                if nums[lo] <= target < nums[mid]:
                    hi = mid - 1
                else:
                    lo = mid + 1
            else:
                if nums[mid] < target <= nums[hi]:
                    lo = mid + 1
                else:
                    hi = mid - 1
        return False
Explanation:

  1. Same rotated-array logic as LC 33, but when nums[lo] == nums[mid] == nums[hi], we cannot tell which side is sorted.
  2. Shrink boundaries with lo += 1; hi -= 1 — worst case degrades to O(n).
  3. Follow-up answer: duplicates can force linear time because equal values at both ends hide the pivot.

Time: O(log n) average, O(n) worst  |  Space: O(1)

1
2
3
class Solution:
    def search(self, nums: list[int], target: int) -> bool:
        return target in nums
Explanation:

  1. Simple O(n) scan; always correct regardless of duplicates.
  2. When many duplicates cluster at the boundaries, BS may also approach O(n), so the gap narrows.
  3. In practice, Approach 1 still skips large sorted runs in O(log n) on typical inputs.

Time: O(n)  |  Space: O(1)

5. Lower Bound / Upper Bound#

Problem 1: Longest Increasing Subsequence (Leetcode:300)#

Problem Statement

Given an integer array nums, return the length of the longest strictly increasing subsequence**.

Example 1:

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Example 2:

Input: nums = [0,1,0,3,2,3]
Output: 4

Example 3:

Input: nums = [7,7,7,7,7,7,7]
Output: 1

Constraints:

  • 1 <= nums.length <= 2500
  • -104 <= nums[i] <= 104

Follow up: Can you come up with an algorithm that runs in O(n log(n)) time complexity?

Code and Explanation 

1
2
3
4
5
6
7
8
9
class Solution:
    def lengthOfLIS(self, nums: list[int]) -> int:
        n = len(nums)
        dp = [1] * n
        for i in range(n):
            for j in range(i):
                if nums[j] < nums[i]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return max(dp)
Explanation:

  1. dp[i] = length of LIS ending at index i.
  2. For each i, extend every earlier j where nums[j] < nums[i].
  3. Correct baseline before optimizing with lower bound on a tails array.

Time: O(n²)  |  Space: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
import bisect

class Solution:
    def lengthOfLIS(self, nums: list[int]) -> int:
        tails = []
        for num in nums:
            pos = bisect.bisect_left(tails, num)
            if pos == len(tails):
                tails.append(num)
            else:
                tails[pos] = num
        return len(tails)
Explanation:

  1. tails[len] = smallest tail value of any increasing subsequence of length len + 1.
  2. For each num, lower bound (bisect_left) finds where to place it in tails.
  3. If num exceeds all tails, extend LIS length; otherwise replace to keep tails minimal.
  4. Length of tails is the LIS length — classic lower_bound application outside sorted input arrays.

Time: O(n log n)  |  Space: O(n)

Problem 2: Find Smallest Letter Greater Than Target (Leetcode:744)#

Problem Statement

You are given an array of lowercase letters letters sorted in non-decreasing order, and a character target. There will be at least one letter in the array that is lexicographically greater than target.

Return the smallest character in the array that is lexicographically greater than target.

Example 1:

Input: letters = ["c","f","j"], target = "a"
Output: "c"

Example 2:

Input: letters = ["c","f","j"], target = "c"
Output: "f"

Example 3:

Input: letters = ["x","x","y","y"], target = "z"
Output: "x"
Explanation: Wrap-around: no letter is greater than z, so return the smallest letter.

Constraints:

  • 2 <= letters.length <= 104
  • letters[i] is a lowercase English letter.
  • letters is sorted in non-decreasing order.
  • letters contains at least two different characters.
  • target is a lowercase English letter.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def nextGreatestLetter(self, letters: list[str], target: str) -> str:
        lo, hi = 0, len(letters)
        while lo < hi:
            mid = lo + (hi - lo) // 2
            if letters[mid] > target:
                hi = mid
            else:
                lo = mid + 1
        return letters[lo % len(letters)]
Explanation:

  1. Find the first index where letters[i] > target — lower bound on the strict predicate > target (not >=).
  2. If lo == len(letters), every letter is <= target; wrap with lo % len(letters).
  3. Direct application of the upper-bound / first-greater template from the theory section.

Time: O(log n)  |  Space: O(1)

1
2
3
4
5
6
class Solution:
    def nextGreatestLetter(self, letters: list[str], target: str) -> str:
        for ch in letters:
            if ch > target:
                return ch
        return letters[0]
Explanation:

  1. Scan sorted letters until finding the first character greater than target.
  2. If none found, return letters[0] for circular wrap-around.
  3. O(n) but trivial to implement; binary search matters on large inputs.

Time: O(n)  |  Space: O(1)

6. Predicate / Boolean Function#

Problem 1: First Bad Version (Leetcode:278)#

Problem Statement

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Example 1:

Input: n = 5, bad = 4
Output: 4
Explanation:
call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true
Then 4 is the first bad version.

Example 2:

Input: n = 1, bad = 1
Output: 1

Constraints:

  • 1 <= bad <= n <= 231 - 1
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
# The isBadVersion API is defined for you.
# def isBadVersion(version: int) -> bool:

class Solution:
    def firstBadVersion(self, n: int) -> int:
        lo, hi = 1, n
        while lo < hi:
            mid = lo + (hi - lo) // 2
            if isBadVersion(mid):
                hi = mid
            else:
                lo = mid + 1
        return lo
Explanation:

  1. Predicate isBadVersion(v) is false…false, true…true — classic lower bound on a boolean array.
  2. If mid is bad, the first bad version is at or before mid → hi = mid.
  3. Minimizes API calls to O(log n).

Time: O(log n)  |  Space: O(1)

1
2
3
4
5
6
class Solution:
    def firstBadVersion(self, n: int) -> int:
        for version in range(1, n + 1):
            if isBadVersion(version):
                return version
        return n
Explanation:

  1. Check versions 1, 2, 3, … until the first bad one.
  2. O(n) API calls — unacceptable when n is up to 2³¹.
  3. Shows why predicate binary search is the intended pattern here.

Time: O(n)  |  Space: O(1)

Problem 2: Find Peak Element (Leetcode:162)#

Problem Statement

A peak element is an element that is strictly greater than its neighbors.

Given a 0-indexed integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.

You may imagine that nums[-1] = nums[n] = -∞. In other words, an element is always considered to be strictly greater than a neighbor that is outside the array.

You must write an algorithm that runs in O(log n) time.

Example 1:

Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.

Example 2:

Input: nums = [1,2,1,3,5,6,4]
Output: 5
Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.

Constraints:

  • 1 <= nums.length <= 1000
  • -231 <= nums[i] <= 231 - 1
  • nums[i] != nums[i + 1] for all valid i.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def findPeakElement(self, nums: list[int]) -> int:
        lo, hi = 0, len(nums) - 1
        while lo < hi:
            mid = lo + (hi - lo) // 2
            if nums[mid] < nums[mid + 1]:
                lo = mid + 1
            else:
                hi = mid
        return lo
Explanation:

  1. If nums[mid] < nums[mid + 1], a peak must exist to the right (ascending slope).
  2. Otherwise a peak is at mid or to the left — set hi = mid.
  3. Virtual -∞ boundaries guarantee a peak exists; adjacent elements are distinct.

Time: O(log n)  |  Space: O(1)

1
2
3
4
5
6
class Solution:
    def findPeakElement(self, nums: list[int]) -> int:
        for i in range(len(nums) - 1):
            if nums[i] > nums[i + 1]:
                return i
        return len(nums) - 1
Explanation:

  1. Return the first index where the next value is smaller — a local peak.
  2. O(n) but straightforward; binary search exploits the slope monotonicity property.

Time: O(n)  |  Space: O(1)

Problem 3: Sqrt(x) (Leetcode:69)#

Problem Statement

Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well.

You must not use any built-in exponent function or operator.

  • For example, do not use pow(x, 0.5) in c++ or x ** 0.5 in python.

Example 1:

Input: x = 4
Output: 2
Explanation: The square root of 4 is 2, so we return 2.

Example 2:

Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since we round it down to the nearest integer, 2 is returned.

Constraints:

  • 0 <= x <= 231 - 1
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def mySqrt(self, x: int) -> int:
        if x < 2:
            return x
        lo, hi = 1, x // 2
        while lo < hi:
            mid = lo + (hi - lo + 1) // 2   # bias up to avoid infinite loop
            if mid * mid <= x:
                lo = mid
            else:
                hi = mid - 1
        return lo
Explanation:

  1. Search the largest integer mid such that mid * mid <= x — binary search on the answer space [1, x // 2].
  2. Predicate mid * mid <= x is monotonic; use upper-mid bias when shrinking lo to prevent stalling.
  3. Handle x = 0 and x = 1 as base cases.

Time: O(log x)  |  Space: O(1)

1
2
3
4
5
6
class Solution:
    def mySqrt(self, x: int) -> int:
        ans = 0
        while (ans + 1) * (ans + 1) <= x:
            ans += 1
        return ans
Explanation:

  1. Increment ans while (ans + 1)² <= x.
  2. Returns floor(sqrt(x)) but takes O(√x) steps — fine for small x, not for 2³¹.
  3. Contrasts with logarithmic search on the integer answer range.

Time: O(√x)  |  Space: O(1)

Problem 1: Search a 2D Matrix (Leetcode:74)#

Problem Statement

You are given an m x n integer matrix matrix with the following two properties:

  • Each row is sorted in non-decreasing order.
  • The first integer of each row is greater than the last integer of the previous row.

Given an integer target, return true if target is in matrix or false otherwise.

You must write a solution in O(log(m * n)) time complexity.

Example 1:


Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

Example 2:


Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false

Constraints:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 100
  • -104 <= matrix[i][j], target <= 104
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def searchMatrix(self, matrix: list[list[int]], target: int) -> bool:
        if not matrix or not matrix[0]:
            return False
        m, n = len(matrix), len(matrix[0])
        lo, hi = 0, m * n - 1
        while lo <= hi:
            mid = lo + (hi - lo) // 2
            val = matrix[mid // n][mid % n]
            if val == target:
                return True
            if val < target:
                lo = mid + 1
            else:
                hi = mid - 1
        return False
Explanation:

  1. Row-major order makes the matrix behave like a sorted 1D array of length m * n.
  2. Map flat index mid to (mid // n, mid % n).
  3. Standard binary search on the virtual array achieves O(log(mn)).

Time: O(log(mn))  |  Space: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def searchMatrix(self, matrix: list[list[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])

        lo, hi = 0, m - 1
        while lo <= hi:
            mid = lo + (hi - lo) // 2
            if matrix[mid][0] <= target <= matrix[mid][-1]:
                row = matrix[mid]
                rlo, rhi = 0, n - 1
                while rlo <= rhi:
                    rm = rlo + (rhi - rlo) // 2
                    if row[rm] == target:
                        return True
                    if row[rm] < target:
                        rlo = rm + 1
                    else:
                        rhi = rm - 1
                return False
            if target < matrix[mid][0]:
                hi = mid - 1
            else:
                lo = mid + 1
        return False
Explanation:

  1. Binary search rows by comparing target with the first and last element of each row.
  2. Once the candidate row is found, binary search within that row.
  3. Still O(log m + log n) = O(log(mn)); more intuitive when thinking row-by-row.

Time: O(log m + log n)  |  Space: O(1)