# Binary Search — Part 2: Interview Problems

Six problems across the three flavours: exact match, boundaries, rotated arrays, search on the answer, and the hard partition search.

## 1. Binary Search (LeetCode 704)

**🟢 Easy.** Return the index of `target` in the sorted array `nums`, or −1.

```text
nums = [-1,0,3,5,9,12], target = 9 → 4
```

**Approach.** Lower bound, then check that the element there equals the target.

**Complexity.** O(log n) time, O(1) space.

```typescript
function search(nums: number[], target: number): number {
  let lo = 0, hi = nums.length;
  while (lo < hi) {
    const mid = (lo + hi) >>> 1;
    if (nums[mid] < target) lo = mid + 1; else hi = mid;
  }
  return lo < nums.length && nums[lo] === target ? lo : -1;
}
```

```python
def search(nums, target):
    lo, hi = 0, len(nums)
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo if lo < len(nums) and nums[lo] == target else -1
```

## 2. Find First and Last Position of Element (LeetCode 34)

**🟠 Medium.** Return `[first, last]` positions of `target` in sorted `nums`, or `[-1, -1]`, in O(log n).

```text
nums = [5,7,7,8,8,10], target = 8 → [3,4]
```

**Approach.** `first = lower_bound(target)`, `last = lower_bound(target + 1) − 1` (or upper_bound − 1). If `first` is out of range or doesn't hold the target, return `[-1, -1]`.

**Complexity.** O(log n) time.

```typescript
function lowerBound(nums: number[], x: number): number {
  let lo = 0, hi = nums.length;
  while (lo < hi) { const mid = (lo + hi) >>> 1; if (nums[mid] < x) lo = mid + 1; else hi = mid; }
  return lo;
}

function searchRange(nums: number[], target: number): number[] {
  const first = lowerBound(nums, target);
  if (first === nums.length || nums[first] !== target) return [-1, -1];
  return [first, lowerBound(nums, target + 1) - 1];
}
```

```python
from bisect import bisect_left

def search_range(nums, target):
    first = bisect_left(nums, target)
    if first == len(nums) or nums[first] != target:
        return [-1, -1]
    return [first, bisect_left(nums, target + 1) - 1]
```

## 3. Search in Rotated Sorted Array (LeetCode 33)

**🟠 Medium.** A sorted array of distinct values was rotated at an unknown pivot. Return the index of `target` or −1 in O(log n).

```text
nums = [4,5,6,7,0,1,2], target = 0 → 4
```

**Approach.** At every step one half of `[lo, hi]` is sorted. If `nums[lo] <= nums[mid]`, the left half is sorted: go left if `nums[lo] <= target < nums[mid]`, otherwise right. Else the right half is sorted: go right if `nums[mid] < target <= nums[hi]`.

**Complexity.** O(log n) time, O(1) space.

```typescript
function searchRotated(nums: number[], target: number): number {
  let lo = 0, hi = nums.length - 1;
  while (lo <= hi) {
    const mid = (lo + hi) >>> 1;
    if (nums[mid] === target) return mid;
    if (nums[lo] <= nums[mid]) {
      if (nums[lo] <= target && target < nums[mid]) hi = mid - 1; else lo = mid + 1;
    } else {
      if (nums[mid] < target && target <= nums[hi]) lo = mid + 1; else hi = mid - 1;
    }
  }
  return -1;
}
```

```python
def search_rotated(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[lo] <= nums[mid]:                    # left half sorted
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:                                        # right half sorted
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1
```

## 4. Find Minimum in Rotated Sorted Array (LeetCode 153)

**🟠 Medium.** Return the minimum of a rotated sorted array of distinct values in O(log n).

```text
nums = [3,4,5,1,2] → 1
```

**Approach.** Compare `nums[mid]` with `nums[hi]`: if `nums[mid] > nums[hi]`, the drop (and the minimum) is to the right of mid; otherwise the minimum is at mid or to its left.

**Complexity.** O(log n) time.

```typescript
function findMin(nums: number[]): number {
  let lo = 0, hi = nums.length - 1;
  while (lo < hi) {
    const mid = (lo + hi) >>> 1;
    if (nums[mid] > nums[hi]) lo = mid + 1; else hi = mid;
  }
  return nums[lo];
}
```

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

## 5. Koko Eating Bananas (LeetCode 875)

**🟠 Medium.** Koko eats at speed k bananas/hour, one pile per hour at most (leftover hours are wasted). Return the minimum k that finishes all `piles` within `h` hours.

```text
piles = [3,6,7,11], h = 8 → 4
```

**Approach.** Search on the answer. Speeds range from 1 to `max(piles)`. `hours(k) = Σ ceil(pile / k)` decreases as k grows (monotonic), so binary search the smallest k with `hours(k) ≤ h`.

**Complexity.** O(n log max(piles)) time, O(1) space.

```typescript
function minEatingSpeed(piles: number[], h: number): number {
  const hours = (k: number) => piles.reduce((t, p) => t + Math.ceil(p / k), 0);
  let lo = 1, hi = Math.max(...piles);
  while (lo < hi) {
    const mid = (lo + hi) >>> 1;
    if (hours(mid) <= h) hi = mid; else lo = mid + 1;
  }
  return lo;
}
```

```python
def min_eating_speed(piles, h):
    def hours(k):
        return sum((p + k - 1) // k for p in piles)   # ceil division
    lo, hi = 1, max(piles)
    while lo < hi:
        mid = (lo + hi) // 2
        if hours(mid) <= h:
            hi = mid
        else:
            lo = mid + 1
    return lo
```

## 6. Median of Two Sorted Arrays (LeetCode 4)

**🔴 Hard.** Return the median of two sorted arrays in O(log(min(m, n))).

```text
a = [1,2], b = [3,4] → 2.5
```

**Approach.** Binary search a **partition** of the shorter array A: take i elements from A and j = half − i from B so the left side holds half of all elements. The partition is correct when `A[i−1] ≤ B[j]` and `B[j−1] ≤ A[i]`; if `A[i−1] > B[j]`, take fewer from A (move left), else more. The median comes from the max of the left side and the min of the right side.

**Complexity.** O(log min(m, n)) time, O(1) space.

```typescript
function findMedianSortedArrays(a: number[], b: number[]): number {
  if (a.length > b.length) [a, b] = [b, a];
  const m = a.length, n = b.length, half = (m + n + 1) >> 1;
  let lo = 0, hi = m;
  while (lo <= hi) {
    const i = (lo + hi) >> 1, j = half - i;
    const aL = i > 0 ? a[i - 1] : -Infinity, aR = i < m ? a[i] : Infinity;
    const bL = j > 0 ? b[j - 1] : -Infinity, bR = j < n ? b[j] : Infinity;
    if (aL <= bR && bL <= aR) {
      return (m + n) % 2 ? Math.max(aL, bL) : (Math.max(aL, bL) + Math.min(aR, bR)) / 2;
    }
    if (aL > bR) hi = i - 1; else lo = i + 1;
  }
  return 0;
}
```

```python
def find_median_sorted_arrays(a, b):
    if len(a) > len(b):
        a, b = b, a
    m, n = len(a), len(b)
    half = (m + n + 1) // 2
    lo, hi = 0, m
    while lo <= hi:
        i = (lo + hi) // 2
        j = half - i
        a_left = a[i - 1] if i > 0 else float("-inf")
        a_right = a[i] if i < m else float("inf")
        b_left = b[j - 1] if j > 0 else float("-inf")
        b_right = b[j] if j < n else float("inf")
        if a_left <= b_right and b_left <= a_right:
            if (m + n) % 2:
                return float(max(a_left, b_left))
            return (max(a_left, b_left) + min(a_right, b_right)) / 2
        if a_left > b_right:
            hi = i - 1
        else:
            lo = i + 1
    return 0.0
```