# Binary search

## Intro

Binary Search splits the search space into two halves and only keep the half that has the search target and throw away the other half that would not have the target. In each step, the search space is reduced to half, until the target is found. Binary Search reduces the search time from linear O(n) to logarithmic O(log n).

## Generalized binary search template

For an array(not only for numbers) sorted in ascending order, the following is the generalized binary search template to solve many problems.

1 | def binary_search(array) -> int: |

Note:

- The left and right are the boundary to include all possible elements(aka search space)
- Is return value left or left - 1? Remember this: after exiting the while loop, left is the minimal k satisfying the condition function
- Design the condition function. Let’s get more sense with the following practices.

Thanks to **zhijun_liao** who wrote this useful binary search article.

## Basic application

### [Leetcode 35] Search Insert Position

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:

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

Example 2:

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

Example 3:

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

Constraints:

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

Solution:

1 | class Solution: |

### [Leetcode 69] Sqrt(x)

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:

1 | Input: x = 4 |

Example 2:

1 | Input: x = 8 |

Constraints:

- 0 <= x <= 231 - 1

Solution:

1 | class Solution: |

### [Leetcode 278] First Bad Version

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:

1 | Input: n = 5, bad = 4 |

Example 2:

1 | Input: n = 1, bad = 1 |

Constraints:

- 1 <= bad <= n <= 231 - 1

Solution:

1 | class Solution: |

## Advanced application

### [Leetcode 668] Kth Smallest Number in Multiplication Table

Nearly everyone has used the Multiplication Table. The multiplication table of size m x n is an integer matrix mat where mat[i][j] == i * j (1-indexed).

Given three integers m, n, and k, return the kth smallest element in the m x n multiplication table.

Example :

1 | Input: m = 3, n = 3, k = 5 |

Solution:

1 | class Solution: |

### [Leetcode 719] Find K-th Smallest Pair Distance

The distance of a pair of integers a and b is defined as the absolute difference between a and b.

Given an integer array nums and an integer k, return the kth smallest distance among all the pairs nums[i] and nums[j] where 0 <= i < j < nums.length.

Example 1:

1 | Input: nums = [1,3,1], k = 1 |

Example 2:

1 | Input: nums = [1,1,1], k = 2 |

Example 3:

1 | Input: nums = [1,6,1], k = 3 |

Constraints:

- n == nums.length
- 2 <= n <= 104
- 0 <= nums[i] <= 106
- 1 <= k <= n * (n - 1) / 2

Solution:

Brute force with priority queue:

1 | def smallestDistancePair_time_limit_exceeded(self, nums: List[int], k: int) -> int: |

Binary search:

1 | class Solution: |

### [Leetcode 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 1:

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

Solution:

1 | class Solution: |

### [Leetcode 1011] Capacity To Ship Packages Within D Days

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:

1 | Input: weights = [1,2,3,4,5,6,7,8,9,10], days = 5 |

Solution:

1 | class Solution: |

### [Leetcode 1201] Ugly Number III

An ugly number is a positive integer that is divisible by a, b, or c.

Given four integers n, a, b, and c, return the nth ugly number.

Example 1:

1 | Input: n = 3, a = 2, b = 3, c = 5 |

Example 2:

1 | Input: n = 4, a = 2, b = 3, c = 4 |

Example 3:

1 | Input: n = 5, a = 2, b = 11, c = 13 |

Constraints:

- 1 <= n, a, b, c <= 10^9
- 1 <= a * b * c <= 10^18
- It is guaranteed that the result will be in range [1, 2 * 10^9].

Solution:

1 | import math |

### [Leetcode 1283] Find the Smallest Divisor Given a Threshold

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:

1 | Input: nums = [1,2,5,9], threshold = 6 |

Example 2:

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

Constraints:

- 1 <= nums.length <= 5 * 10^4
- 1 <= nums[i] <= 10^6
- nums.length <= threshold <= 10^6

Solution:

1 | class Solution: |

## More practices

### [Leetcode 162] Find Peak Element

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:

1 | Input: nums = [1,2,3,1] |

Example 2:

1 | Input: nums = [1,2,1,3,5,6,4] |

Constraints:

- 1 <= nums.length <= 1000
- -2^31 <= nums[i] <= 2^31 - 1
- nums[i] != nums[i + 1] for all valid i.

Solution:

1 | class Solution: |

### [Leetcode 2300] Successful Pairs of Spells and Potions

You are given two positive integer arrays spells and potions, of length n and m respectively, where spells[i] represents the strength of the ith spell and potions[j] represents the strength of the jth potion.

You are also given an integer success. A spell and potion pair is considered successful if the product of their strengths is at least success.

Return an integer array pairs of length n where pairs[i] is the number of potions that will form a successful pair with the ith spell.

Example 1:

1 | Input: spells = [5,1,3], potions = [1,2,3,4,5], success = 7 |

Constraints:

- n == spells.length
- m == potions.length
- 1 <= n, m <= 105
- 1 <= spells[i], potions[i] <= 105
- 1 <= success <= 1010

Solution:

1 | class Solution: |