# 23. Binary Search

## Table of Contents

## A. Introduction

## B. LeeCode Problems

### 704. Binary Search

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:

Input:nums = [-1,0,3,5,9,12], target = 9

Output:4

Explanation:9 exists in nums and its index is 4

## Code

```
class Solution:
def search(self, nums: List[int], target: int) -> int:
"""
0, 1, 2, 3, 4, 5
-1, 0, 3, 5, 9, 12
lr
0+5//2 = 2
0+1//2 = 0
"""
if not nums:
return -1
l,r = 0, len(nums)-1
while l <= r:
mid = (l + r)//2
if nums[mid] == target:
return mid
elif nums[mid] < target:
l = mid + 1
else:
r = mid - 1
return -1
```

### 74. Search a 2D Matrix

Write an efficient algorithm that searches for a value `target`

in an `m x n`

integer matrix `matrix`

. This matrix has the following properties:

- Integers in each row are sorted from left to right
- The first integer of each row is greater than the last integer of the previous row

Example:

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

Output:true

## Code

#### Key Ideas

- The matrix can be treated as a sorted array
- Perform binary search on the rows to find the row where the target can be found
- If the target is greater than the last element of the row, then the target can be found in the next row
- If the target is less than the first element of the row, then the target can be found in the previous row

- Implement 1D binary search on the row to find the target

```
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
t,b = 0, len(matrix)-1
while t <= b :
row = (t+b)//2
if matrix[row][-1] < target:
t = row + 1
elif matrix[row][0] > target:
b = row - 1
else:
break
if t > b:
return False
# binary search on the row
l,r = 0, len(matrix[0])-1
while l <= r:
mid = (l+r)//2
if matrix[row][mid] == target:
return True
elif matrix[row][mid] < target:
l = mid + 1
else:
r = mid -1
return False
```

### 875. Koko Eating Bananas

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:

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

Output:4

#### Key Ideas

- The
`k`

can be found iteratively using binary search- Search for a
`k`

that satisfies the condition that the number of hours required to eat all the bananas is less than or equal to`h`

- Search for a
`@BaseCase`

The maximum value of`k`

is the maximum value of the`piles`

## Code

```
import math
class Solution:
def minEatingSpeed(self, piles: List[int], h: int) -> int:
maxPiles = max(piles)
l,r = 1, maxPiles
res = maxPiles
while l <= r:
hrs = 0
k = (l+r)//2
for pile in piles:
hrs += math.ceil(pile/k)
if hrs <= h:
res = min(res, k)
r = k-1
else:
l = k+1
return res
```

### 4. Median of Two Sorted Arrays

Given two sorted arrays `nums1`

and `nums2`

of size `m`

and `n`

respectively, return **the median** of the two sorted arrays.

The overall run time complexity should be `O(log (m+n))`

.

Example:

Input:nums1 = [1,3], nums2 = [2]

Output:2.00000

Explanation:merged array = [1,2,3] and median is 2.

#### Key Ideas

`@KeyAlgorithm`

Binary Search on the smaller array to find the partition point- Move the partition point based on the following condition
$$B_{min}\le A_{max} \ \text{and} \ B_{max} \ge A_{min}$$
- If the above condition is satisfied, then the array is partitioned right
- Even, median = $(max(A_{min}, B_{min})+min(A_{max}, B_{max}))/2$
- Odd, median = $min(A_{max}, B_{max})$

- If $B_{min}$ is greater than $A_{max}$, then
`l`

is moved to`mid+1`

- If $B_{max}$ is less than $A_{min}$, then
`r`

is moved to`mid-1`

- If the above condition is satisfied, then the array is partitioned right

- Move the partition point based on the following condition
$$B_{min}\le A_{max} \ \text{and} \ B_{max} \ge A_{min}$$

## Code

```
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
if len(nums1) > len(nums2):
nums2, nums1 = nums1, nums2
m,n = len(nums1), len(nums2)
total_len = m+n
half = total_len//2
l,r = 0, m-1
while True:
a_mid = (l+r)//2
Amin = nums1[a_mid] if a_mid >= 0 else float("-inf")
Amax = nums1[a_mid+1] if a_mid+1 < m else float("inf")
b_mid = half-a_mid-2 # both a_mid and half needs to be zero indexed
Bmin = nums2[b_mid] if b_mid >= 0 else float("-inf")
Bmax = nums2[b_mid+1] if b_mid+1 < n else float("inf")
if Bmin <= Amax and Bmax >= Amin:
if total_len % 2 == 0:
return (max(Amin, Bmin)+min(Amax, Bmax))/2
return min(Amax, Bmax)
elif Bmin > Amax:
l = a_mid + 1
else:
r = a_mid - 1
```