69. x 的平方根(Easy)
class Solution(object): def mySqrt(self, x): left, right = 1, x while (left <= right): mid = (left + right) // 2 if mid * mid <= x: left = mid + 1 else: right = mid - 1 return right
744. 寻找比目标字母大的最小字母(Easy)
class Solution(object): def nextGreatestLetter(self, letters, target): left, right = 0, len(letters) - 1 while left <= right: mid = (left + right) // 2 if letters[mid] <= target: left = mid + 1 else: right = mid - 1 return letters[0] if left == len(letters) else letters[left]
class Solution(object): def nextGreatestLetter(self, letters, target): index = bisect.bisect(letters, target) return letters[index%len(letters)]
540. 有序数组中的单一元素(Medium)
问题分析:
二分法,每次让 mid 位于序号为 0,2,4,6… 的偶数的元素上。
如果目标元素在 mid 右边,一定有 nums[mid]==nums[mid+1],目标元素范围更新为 [mid+2,right];
如果目标元素为 mid 或者在 mid 左边,一定有 nums[mid]!=nums[mid+1],目标元素范围更新为 [left,mid]。
class Solution(object): def singleNonDuplicate(self, nums): left, right = 0, len(nums) - 1 while left < right: mid = (left + right) // 2 if mid % 2: mid -= 1 if nums[mid] == nums[mid + 1]: left = mid + 2 else: right = mid return nums[left]
时间复杂度:O(log(n/2)) = O(logn),对元素的一半进行二分搜索。
空间复杂度:O(1)
278. 第一个错误的版本(Easy)
# The isBadVersion API is already defined for you. # @param version, an integer # @return a bool # def isBadVersion(version): class Solution(object): def firstBadVersion(self, n): left, right = 1, n while left < right: mid = (left + right)//2 if isBadVersion(mid): right = mid else: left = mid + 1 return left
153. 寻找旋转排序数组中的最小值(Medium)
旋转之后,右侧的数据一定小于左侧的数据,如果 nums[mid]>nums[right],则最小值在 mid 右侧,新的区间更新为 [mid+1,right], nums[mid]<nums[right],则最小值在 mid 及 mid 左侧,区间更新为 [left,mid]
class Solution(object): def findMin(self, nums): left, right = 0, len(nums)-1 while left < right: mid = (left + right)//2 if nums[mid] > nums[right]: left = mid + 1 else: right = mid return nums[left]
34. 在排序数组中查找元素的第一个和最后一个位置(Medium)
先找第一个大于等于 target 的元素下标,再找第一个大于等于 target+1 的元素下标
class Solution(object): def searchRange(self, nums, target): def insert_index(nums, x): left, right = 0, len(nums) while left < right: mid = (left + right) // 2 if nums[mid] < x: left = mid + 1 else: right = mid return left if not nums or target > nums[-1]: return [-1, -1] low = insert_index(nums, target) if target != nums[low]: return [-1, -1] high = insert_index(nums, target + 1) - 1 return [low, high]