二分查找及变体

简介

二分查找（binary search）是一种基于分治策略的高效搜索算法。它利用数据的有序性，每轮缩小一半搜索范围，直至找到目标元素或搜索区间为空为止。
学习视频：代码随想录-二分查找

常见的用法有三种：

• 查找目标元素的位置：即目标元素的位置
• 查找目标元素的下界（lower bound）：小于目标元素的第一个位置
• 查找目标元素的上界（upper bound）：大于目标元素的第一个位置

练习题

704. 二分查找

思路

• 经典的二分查找；
• 直接实现即可。

代码

class Solution(object):def search(self, nums, target):""":type nums: List[int]:type target: int:rtype: int"""l, r = 0, len(nums) - 1while(l <= r):m = l + (r - l) // 2if nums[m] > target:r = m - 1elif nums[m] < target:l = m + 1else:return mreturn -1

35. 搜索插入位置

思路

• 类lowerbound查找；
• 时刻清楚边界的条件：while结束时区间情况为[r, l]，r位置元素比target小，l位置即为待插入的位置。

代码

class Solution(object):
class Solution(object):def searchInsert(self, nums, target):""":type nums: List[int]:type target: int:rtype: int"""l, r = 0, len(nums) - 1while l <= r:m = l + (r - l) // 2if nums[m] > target:r = m - 1elif nums[m] < target:l = m + 1else:return mreturn l

34. 在排序数组中查找元素的第一个和最后一个位置

思路

• 考虑upperbound和lowerbound
• lowerbound:：每次把区间往左边压缩，结束判断边界元素
• upperbound：每次把区间往右边压缩，结束时判断边界元素

代码

class Solution(object):def searchRange(self, nums, target):""":type nums: List[int]:type target: int:rtype: List[int]"""n = len(nums)if n == 0:return [-1, -1]elif n == 1:return [0, 0] if nums[0] == target else [-1, -1]l, r = 0, n - 1ans = [-1, -1]while l <= r: // lower boundm = (l + r) // 2if nums[m] >= target:r = m - 1else:l = m + 1if l < n and nums[l] == target:ans[0] = ll, r = 0, n - 1while l <= r: // upper boundm = (l + r) // 2if nums[m] > target:r = m - 1else:l = m + 1if r < n and nums[r] == target:ans[1] = rreturn ans