- 寻找一个数
- 寻找重复数(这是个中等题)">寻找重复数(这是个中等题)
- 搜索旋转排序数组">搜索旋转排序数组
- 搜索旋转排序数组 II(数据可能有重复)">搜索旋转排序数组 II(数据可能有重复)
- 寻找旋转排序数组中的最小值">寻找旋转排序数组中的最小值
- 寻找旋转排序数组中的最小值 II(有重复项)">寻找旋转排序数组中的最小值 II(有重复项)
- 两个数组的交集">两个数组的交集
- 两个数组的交集 II">两个数组的交集 II
- 寻找峰值">寻找峰值
- 在排序数组中查找元素的第一个和最后一个位置">在排序数组中查找元素的第一个和最后一个位置
- 寻找比目标字母大的最小字母">寻找比目标字母大的最小字母
- 找到 K 个最接近的元素*">找到 K 个最接近的元素*
- x 的平方根">x 的平方根
- 有效的完全平方数">有效的完全平方数
前提条件:有序
最常用的二分查找场景:寻找一个数、寻找左侧边界、寻找右侧边界。
二分查找框架
def binary_search(alist, item):
left = 0
right = len(alist) - 1
while ...:
mid = left + (right - left) // 2
if alist[mid] == item:
return ...
elif item < alist[mid]:
right = ...
else:
left = ...
return ...
注意:计算 mid 时需要防止溢出,代码中 left + (right - left) / 2
和 (left + right) / 2
的结果相同,但是有效防止了 left
和 right
太大直接相加导致溢出。
二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。
寻找一个数
class Solution(object):
def search(self, nums, target):
'''二分查找,递归'''
if not nums:
return -1
mid = len(nums)//2
if nums[mid] > target:
return self.search(nums[:mid], target)
elif nums[mid] < target:
return self.search(nums[mid+1:], target)
else:
return mid
return -1
class Solution(object):
def search(self, nums, target):
'''二分查找,非递归'''
if not nums:
return -1
left = 0
right = len(nums) - 1
while left < right:
mid = (left + right)//2
if nums[mid] > target:
right = mid - 1
elif nums[mid] < target:
left = mid + 1
else:
return mid
return -1
寻找重复数(这是个中等题)
给定一个包含 n + 1 个整数的数组 nums ,其数字都在 1 到 n 之间(包括 1 和 n),可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 ,找出 这个重复的数 。
输入:nums = [1,3,4,2,2]
输出:2
输入:nums = [3,1,3,4,2]
输出:3
class Solution(object):
def findDuplicate(self, nums):
# 方法一:我怎么也没想到,这竟然能和环形链表扯上关系
pre = nums[0]
cur = nums[nums[0]]
while pre != cur:
pre = nums[pre]
cur = nums[nums[cur]]
pre = 0
while pre != cur:
pre = nums[pre]
cur = nums[cur]
return cur
# 方法二:快慢指针
left = 1
right = len(nums) - 1
while left < right:
mid = (right + left ) // 2
# 计数, 找小于等于mid的个数
cnt = 0
for num in nums:
if num <= mid:
cnt += 1
# <= 说明 重复元素再右半边
if cnt <= mid:
left = mid + 1
else:
right = mid
return left
# 方法三:散列表解法
dicts = {}
for i in range(len(nums)):
if nums[i] in dicts:
return nums[i]
else:
dicts[nums[i]] = 1
return False
搜索旋转排序数组
给你 旋转后 的数组 nums 和一个整数 target ,如果 nums 中存在这个目标值 target ,则返回它的索引,否则返回 -1 。
输入:nums = [4,5,6,7,0,1,2], target = 0
输出:4
输入:nums = [4,5,6,7,0,1,2], target = 3
输出:-1
class Solution(object):
def search(self, nums, target):
if len(nums) == 0:
return -1
left = 0
right = len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target: # 如果中间值是目标,直接返回
return mid
if nums[mid] >= nums[left]:
if nums[mid] >= target >= nums[left]:
right = mid - 1
else:
left = mid + 1
else:
if nums[mid] <= target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1
搜索旋转排序数组 II(数据可能有重复)
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如,数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。本题中的 nums
可能包含重复元素。
编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true,否则返回 false。
输入: nums = [2,5,6,0,0,1,2], target = 0
输出: true
输入: nums = [2,5,6,0,0,1,2], target = 3
输出: false
class Solution(object):
def search(self, nums, target):
# 依旧是1的答案,通用
if len(nums) == 0:
return -1
left = 0
right = len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target: # 如果中间值是目标,直接返回
return mid
if nums[mid] >= nums[left]:
if nums[mid] >= target >= nums[left]:
right = mid - 1
else:
left = mid + 1
else:
if nums[mid] <= target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1
寻找旋转排序数组中的最小值
给你一个元素值 互不相同 的数组 nums ,它原来是一个升序排列的数组,并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
输入:nums = [3,4,5,1,2]
输出:1
解释:原数组为 [1,2,3,4,5] ,旋转 3 次得到输入数组。
输入:nums = [4,5,6,7,0,1,2]
输出:0
解释:原数组为 [0,1,2,4,5,6,7] ,旋转 4 次得到输入数组。
class Solution(object):
def findMin(self, nums):
left = 0
right = len(nums)-1
while left < right:
mid = (left+right)//2
if nums[mid] < nums[right]:
right = mid
else:
left = mid + 1
return nums[left]
寻找旋转排序数组中的最小值 II(有重复项)
给你一个可能存在 重复 元素值的数组 nums ,它原来是一个升序排列的数组,并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
输入:nums = [1,3,5]
输出:1
输入:nums = [2,2,2,0,1]
输出:0
class Solution(object):
def findMin(self, nums):
left = 0
right = len(nums) - 1
while left < right:
mid = (left+right)//2
# 如果nums[mid] < nums[right],说明最小值在左边,并且最小值有可能就是nums[mid]
if nums[mid] < nums[right]:
right = mid
# 如果nums[mid] > nums[right],说明最小值在右边
elif nums[mid] > nums[right]:
left = mid + 1
# 相等则r索引递减即可例如处理[1,2,2,2]
else:
right = right - 1
# 返回最后lr指向的值即可
return nums[left]
两个数组的交集
给定两个数组,编写一个函数来计算它们的交集。
输入:nums1 = [1,2,2,1], nums2 = [2,2]
输出:[2]
输入:nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出:[9,4]
class Solution(object):
def intersection(self, nums1, nums2):
dicts = {}
res = []
for i in range(len(nums1)):
if nums1[i] in dicts:
dicts[nums1[i]] += 1
else:
dicts[nums1[i]] = 1
for i in range(len(nums2)):
if nums2[i] in dicts:
res.append(nums2[i])
return list(set(res))
两个数组的交集 II
给定两个数组,编写一个函数来计算它们的交集。
输入:nums1 = [1,2,2,1], nums2 = [2,2]
输出:[2,2]
输入:nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出:[4,9]
class Solution(object):
def intersect(self, nums1, nums2):
dicts = {}
res = []
for i in range(len(nums1)):
if nums1[i] in dicts:
dicts[nums1[i]] += 1
else:
dicts[nums1[i]] = 1
for i in range(len(nums2)):
if nums2[i] in dicts:
# 就比I多了两行代码
if dicts[nums2[i]] > 0:
res.append(nums2[i])
dicts[nums2[i]] -= 1
return res
寻找峰值
峰值元素是指其值大于左右相邻值的元素。
给你一个输入数组 nums,找到峰值元素并返回其索引。数组可能包含多个峰值,在这种情况下,返回 任何一个峰值 所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞ 。
输入:nums = [1,2,3,1]
输出:2
解释:3 是峰值元素,你的函数应该返回其索引 2。
输入:nums = [1,2,1,3,5,6,4]
输出:1 或 5
解释:你的函数可以返回索引 1,其峰值元素为 2;
或者返回索引 5, 其峰值元素为 6。
class Solution(object):
def findPeakElement(self, nums):
# 上坡必有峰
left = 0
right = len(nums)-1
while left < right:
mid = (left+right)//2
if nums[mid] < nums[mid+1]:
left = mid + 1
else:
right = mid
return left
在排序数组中查找元素的第一个和最后一个位置
给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target,返回 [-1, -1]。
进阶:
你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗?
输入:nums = [5,7,7,8,8,10], target = 8
输出:[3,4]
输入:nums = [5,7,7,8,8,10], target = 6
输出:[-1,-1]
输入:nums = [], target = 0
输出:[-1,-1]
class Solution(object):
def searchRange(self, nums, target):
# 使用二分查找找到对应数字,然后在定义另外两个变量扩大窗口找范围
if target not in nums:
return [-1, -1]
left = 0
right = len(nums)-1
while right >= left:
mid = (left + right) // 2
if nums[mid] > target:
right = mid - 1
elif nums[mid] < target:
left = mid + 1
else:
l = r = mid
# 这里需要考虑为0的情况,切记!!!!!!!!!!
while l >= 0 and nums[l] == target:
l -= 1
while r < len(nums) and nums[r] == target:
r += 1
return [l+1, r-1]
return [-1, -1]
寻找比目标字母大的最小字母
给你一个排序后的字符列表 letters ,列表中只包含小写英文字母。另给出一个目标字母 target,请你寻找在这一有序列表里比目标字母大的最小字母。
在比较时,字母是依序循环出现的。举个例子:
如果目标字母 target = ‘z’ 并且字符列表为 letters = [‘a’, ‘b’],则答案返回 ‘a’
输入:
letters = [“c”, “f”, “j”]
target = “a”
输出: “c”
输入:
letters = [“c”, “f”, “j”]
target = “c”
输出: “f”
输入:
letters = [“c”, “f”, “j”]
target = “d”
输出: “f”
输入:
letters = [“c”, “f”, “j”]
target = “g”
输出: “j”
输入:
letters = [“c”, “f”, “j”]
target = “j”
输出: “c”
输入:
letters = [“c”, “f”, “j”]
target = “k”
输出: “c”
class Solution(object):
def nextGreatestLetter(self, letters, target):
if letters[-1] <= target or letters[0] > target:
return letters[0]
left = 0
right = len(letters) - 1
while left < right:
mid = (left + right) // 2
if letters[mid] == target:
# 等于目标值,往右找
left = mid + 1
elif letters[mid] < target:
# 比目标值小,往右找
left = mid + 1
else:
# 比目标值大,可能就是要找的数!
right = mid
return letters[left]
找到 K 个最接近的元素*
给定一个排序好的数组 arr ,两个整数 k 和 x ,从数组中找到最靠近 x(两数之差最小)的 k 个数。返回的结果必须要是按升序排好的。
整数 a 比整数 b 更接近 x 需要满足:
|a - x| < |b - x| 或者
|a - x| == |b - x| 且 a < b
输入:arr = [1,2,3,4,5], k = 4, x = 3
输出:[1,2,3,4]
输入:arr = [1,2,3,4,5], k = 4, x = -1
输出:[1,2,3,4]
class Solution(object):
def findClosestElements(self, arr, k, x):
# 直接定位mid为左边界;
# 查找mid+k的结果是否满足要求;
# 不满足的话二分法左右调整mid。
left = 0
#右 边界减k是因为mid为左边界,后面会使用mid+k进行判断
right = len(arr)-k
while left < right:
mid = (right+left)//2
if x - arr[mid] > arr[mid + k] - x:
left = mid + 1
else :
right = mid
return arr[left : left + k]
x 的平方根
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根,其中 x 是非负整数。
由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。
输入: 4
输出: 2
输入: 8
输出: 2
说明: 8 的平方根是 2.82842…,
由于返回类型是整数,小数部分将被舍去。
class Solution(object):
def mySqrt(self, x):
left = 0
right = x
res = -1
while left <= right:
mid = (left + right)//2
if mid * mid <= x:
res = mid
left = mid + 1
else:
right = mid - 1
return res
有效的完全平方数
给定一个 正整数 num ,编写一个函数,如果 num 是一个完全平方数,则返回 true ,否则返回 false 。
进阶:不要 使用任何内置的库函数,如 sqrt 。
输入:num = 16
输出:true
输入:num = 14
输出:false
class Solution(object):
def isPerfectSquare(self, num):
if num == 1:
return True
if num == 0:
return False
left = 1
right = num
while left < right:
mid = (left+right)//2
if mid*mid > num:
right = mid
elif mid*mid < num:
left = mid + 1
else:
return True
return False