Binary Search Flashcards
- Search in Rotated Sorted Array
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
Your algorithm’s runtime complexity must be in the order of O(log n).
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
跟一般binary search依樣要分左右邊，只是這邊判斷的方式是先分辨左右哪一邊是有序的，然後再判斷target是否在有序的那邊，是的話就在那一半繼續找，不是的話就是另一半。這個演算法可以適用排序好的list，也可以用在有rotate的
- Find First and Last Position of Element in Sorted Array
Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.
Your algorithm’s runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
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]
~~~
~~~
兩次binary search
找start在找end
這題可以用模板 設計g(m) nums[mid] >= target => start 就會是l nums[mid] > target => end 就會是r 還要考慮根本找不到的情況做判斷
- Search a 2D Matrix
Write an efficient algorithm that searches for a value in an m x n 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 1:
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,50]], target = 3
Output: true
Example 2:
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,50]], target = 13
Output: false
Example 3:
Input: matrix = [], target = 0
Output: false
Constraints:
m == matrix.length
n == matrix[i].length
0 <= m, n <= 100
-104 <= matrix[i][j], target <= 104
把2d matrix當成 1d list來操作。l, r=0, m*n-1
i, j = mid / n, mid % n
這要操作以後就是一般的binary search
- Find Minimum in Rotated Sorted Array
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
Find the minimum element.
You may assume no duplicate exists in the array.
Example 1:
Input: [3,4,5,1,2]
Output: 1
Example 2:
Input: [4,5,6,7,0,1,2]
Output: 0
因為這題需要考慮到mid + 1 or mid - 1
所以用這種模板可以讓code比較整潔
class Solution(object):
def findMin(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) == 1: return nums[0]
if nums[0] < nums[-1]: return nums[0]
# 1, 0
# 3, 0, 1, 2
# 1,2,3,0
l, r = 0, len(nums) - 1
while l + 1 < r:
mid = (l + r) // 2
if nums[mid - 1] > nums[mid] and nums[mid + 1] > nums[mid]:
return nums[mid]
elif nums[mid] < nums[0]:
r = mid
else:
l = mid
return nums[r]
- Find Minimum in Rotated Sorted Array II
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
Find the minimum element.
The array may contain duplicates.
Example 1:
Input: [1,3,5]
Output: 1
Example 2:
Input: [2,2,2,0,1]
Output: 0
Note:
This is a follow up problem to Find Minimum in Rotated Sorted Array.
Would allow duplicates affect the run-time complexity? How and why?
如同上一題，只要對nums做一寫整理
把頭尾相同的，從尾巴去掉。
接這就可以用153的解法，只是此刻的最後一個位置都要用r代表
- Find the Smallest Divisor Given a Threshold
Given an array of integers nums and an integer threshold, we will choose a positive integer divisor and divide all the array by it and sum the result of the division. Find the smallest divisor such that the result mentioned above is less than or equal to threshold.
Each result of division is rounded to the nearest integer greater than or equal to that element. (For example: 7/3 = 3 and 10/2 = 5).
It is guaranteed 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 to 7 (1+1+2+3) and if the divisor is 5 the sum will be 5 (1+1+1+2).
Example 2:
Input: nums = [2,3,5,7,11], threshold = 11
Output: 3
Example 3:
Input: nums = [19], threshold = 5
Output: 4
Constraints:
1 <= nums.length <= 5 * 10^4
1 <= nums[i] <= 10^6
nums.length <= threshold <= 10^6
這題需要用binary search去找，重點是要想出l, r範圍，l可以從1開始，r就從max(nums)開始保證res會小於threshold。
這一題用左閉右閉，回傳l，第一個滿足g(m)的點，g(m) = res <= threshold. 不可以遇到res == threshold就return，因為可能有多個res 都== threshold他不一定是最靠近的
