- 思路
- example: [1,3,5], target = 0,1,2,3,4,5,6
- nums = [5], target = 5, ans = 0
- nums = [5], target = 6, ans = 1
- nums = [5], target = 4, ans = 0
- 已排好序，无重复元素
- 类似 “插入位置：第1个>=target的位置”，答案范围：0,1,..., n
- 二分模板2，左闭右开, left = 0, right = n (NOT n-1), while left < right, <, >=; quit when left == right
- 复杂度. 时间：O(log n), 空间: O(1)
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
n = len(nums)
left, right = 0, n
while left < right: # [left, right)
mid = left + (right - left) // 2
if nums[mid] < target:
left = mid + 1
else: # nums[mid] >= target
right = mid
return left # or right
- 用左闭右闭思路更好理解。
- [left, right]表示答案的存在范围，初始left = 0, right = n。
- mid是向下取整的“一半”
- nums[mid] < target：插入位置必在[mid+1, right] （左半部不可能包含答案）
- nums[mid] >= target: 插入位置必在[left, mid], 注意mid仍有可能是答案 （mid右边不可能包含答案）
- 终止条件：left == right, 这个时候mid = left = right, 如果nums[mid] >= target，指针不会有变化，死循环。所以left == right时就停止。
- 最后left == right是由3个元素或2个元素变为1个元素。
－最后return left (或 right)
-
左闭右闭 (用这个版本，可拓展）
- 类似 “插入位置：第1个>=target的位置”，答案范围：0,1,..., n
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
n = len(nums)
left, right = 0, n-1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return left # left \in [0,...,n]
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
n = len(nums)
left, right = 0, n-1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return left # could be n
- 思路
- example
- 已排好序，有重复元素
- 第1个==位置，最后一个==位置
- 二分模板1，左闭右闭, left = 0, right = n-1, while left <= right, ==, >, <; quit when left > right
- type = 'first'
- nums[mid] > target: 答案在[left, mid-1]
- nums[mid] < target: 答案在[mid+1, right]
- nums[mid] == target: 答案在[left, mid], 但是第一个等于target的位置可能在更左边。 为方便，直接去[left, mid-1]找可能的答案。
- while left <= right:
- 最后一步left==right时，判断最可能的答案 （可能越界：n)（return left)。
- type = 'last'
- nums[mid] > target: 答案在[left, mid-1]
- nums[mid] < target: 答案在[mid+1, right]
- nums[mid] == target: 答案在[left, mid], 但是最后一个等于target的位置可能在更右边。 为方便，直接去[mid+1, right]找可能的答案。
- while left <= right:
- 最后一步left==right时，判断最可能的答案 （可能越界：-1)（return right)。
- 复杂度. 时间：O(log n), 空间: O(1)
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
n = len(nums)
def BinarySearch(left, right, type):
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target and type == 'first':
right = mid - 1
elif nums[mid] > target: # both cases
right = mid - 1
else: # 'first': < target; 'last': <= target
left = mid + 1
return left if type == 'first' else right
idx1 = BinarySearch(0, n-1, 'first')
idx2 = BinarySearch(0, n-1, 'last')
if idx1 > idx2: return [-1, -1]
return [idx1, idx2]
-
另一个思路：
- 数组前面加
,后面加
.
-
第一个 >=target 位置: idx1；答案在[0,...,n]中; 左闭右闭二分模板2：while left < right。
-
第一个 >target 位置: idx2，答案在[0,...,n]中; 左闭右闭二分模板2：while left < right。
- 注意要判断idx1是否等于n或者对应数字是否等于target。
- idx2 -= 1得到最后一个<= target 位置。
- mid = left + (right - left) // 2,向下取整（可能等于left)，所以二分写法如果出现left = mid,可能会死循环。
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
def binarySearch_first(nums, target): # search the first position >= target
n = len(nums)
left, right = 0, n-1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] < target:
left = mid + 1
elif nums[mid] > target:
right = mid - 1
else: # nums[mid] == target
right = mid - 1
# now left > right, left in [0,...,n]
return left
def binarySearch_last(nums, target): # search the last position >= target
n = len(nums)
left, right = 0, n-1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] < target:
left = mid + 1
elif nums[mid] > target:
right = mid - 1
else: # ==
left = mid + 1
# now right > left, right in [-1,0,...,n-1]
return right
idx1 = binarySearch_first(nums, target)
if idx1 == n or nums[idx1] != target:
return [-1, -1]
idx2 = binarySearch_last(nums, target)
return [idx1, idx2]
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
def binarySearch_first(nums, target): # 1st index, >= target
n = len(nums)
left, right = 0, n-1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] < target:
left = mid + 1
elif nums[mid] >= target:
right = mid -1
return left
def binarySearch_last(nums, target): # last index, >= target
n = len(nums)
left, right = 0, n-1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] <= target:
left = mid + 1
elif nums[mid] > target:
right = mid -1
return right
n = len(nums)
idx1 = binarySearch_first(nums, target)
if idx1 == n or nums[idx1] != target:
return [-1, -1]
idx2 = binarySearch_last(nums, target)
return [idx1, idx2]
- 思路
- example
- largest k such that k*k <= x
- 二分模板1，左闭右闭, <=, >
- 复杂度. 时间：O(log n), 空间: O(1)
class Solution:
def mySqrt(self, x: int) -> int:
left, right = 0, x
res = 0
while left <= right:
mid = left + (right - left) // 2
num = mid * mid
if num <= x:
res = mid
left = mid + 1
else: # num > x
right = mid - 1
return res
class Solution:
def mySqrt(self, x: int) -> int:
left, right = 0, x
while left <= right:
mid = left + (right - left) // 2
mid2 = mid * mid
if mid2 == x:
return mid
elif mid2 < x:
left = mid + 1
else: # mid2 > x
right = mid - 1
return right
- 思路
- example
- find k such that k*k == num
- 二分模板1，左闭右闭, ==, <, >
- 复杂度. 时间：O(log n), 空间: O(1)
class Solution:
def isPerfectSquare(self, num: int) -> bool:
left, right = 0, num
while left <= right:
mid = left + (right - left) // 2
square = mid * mid
if square == num:
return True
elif square < num:
left = mid + 1
else:
right = mid - 1
return False
