二分查找法
说明：二分查找法在代码实现上有模板方法，一定要掌握。
1、二分查找法的使用前提：数组一定要是排好序的，如果数组不是排好序的，二分查找法便不能使用。
2、实现二分查找法的关键之处：维护循环不变量的定义。如果修改了区间边界的定义，算法得相应改变。
技巧：可以使用小数据量进行测试。
下面给出的问题不是标准的二分查找问题，但是可以用二分查找的思想来解决，稍微要绕一点弯子。其中，第 300 题要用到第 35 题。
LeetCode 第 34 题：在排序数组中查找元素的第一个和最后一个位置
传送门：34. 在排序数组中查找元素的第一个和最后一个位置。
给定一个按照升序排列的整数数组
nums，和一个目标值target。找出给定目标值在数组中的开始位置和结束位置。你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值，返回
[-1, -1]。示例 1:
输入: nums = [5,7,7,8,8,10], target = 8 输出: [3,4]示例 2:
输入: nums = [5,7,7,8,8,10], target = 6 输出: [-1,-1]
思路：使用二分查找，我使用的是二分查找法我认为最好用的模板写法。
1、循环可以继续的条件是 l < r，这样退出循环的时候 l == r 成立，因此就不用纠结返回 l 还是 r 了；
不过要特别注意一点：我们是通过夹逼的方式把搜索的范围逼到一个点，那么这个点是不是符合要求还要单独做判断。
2、循环体比较简单，真正地做到了“二分”，即“写两个分支”作判断，只要分支条件写正确，其中一个分支一定可以排除掉中点，而另一个分支则保留了中点；
3、取“中点”的操作有 2 种，根据循环体的收缩情况，采用合适的中点方法，这一点很重要，否则会出现死循环。
（1）mid = l + (r - l) // 2，特点：在只有两个数的时候，靠近左边。
（2）mid = l + (r - l + 1) // 2，特点：在只有两个数的时候，靠近右边。
例如：循环体是 l = mid + 1 和 r = mid 的时候，表示左端点不断右移，则选择（1），否则会出现死循环；
循环体是 l = mid 和 r = mid - 1 的时候，表示右端点不断左移，则选择（2），否则会出现死循环。
Python 代码：
class Solution:
def searchRange(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
left = self.__find_lower_bound(nums, target)
if left == -1:
return [-1, -1]
right = self.__find_up_bound(nums, target)
return [left, right]
def __find_lower_bound(self, nums, target):
# 找到小于等于 target 的第 1 个元素的索引
size = len(nums)
if size == 0:
return -1
l = 0
r = size - 1
while l < r:
mid = l + (r - l) // 2
if nums[mid] < target:
l = mid + 1
else:
assert nums[mid] >= target
r = mid
# 最后还要单独判断一下
if nums[l] != target:
return -1
return l
def __find_up_bound(self, nums, target):
# 找到大于等于 target 的最后 1 个元素的索引
size = len(nums)
if size == 0:
return -1
l = 0
r = size - 1
while l < r:
mid = l + (r - l + 1) // 2
if nums[mid] > target:
r = mid - 1
else:
assert nums[mid] <= target
l = mid
# 最后还要单独判断一下
if nums[l] != target:
return -1
return l
if __name__ == '__main__':
solution = Solution()
nums = [5, 7, 7, 8, 8, 10]
target = 8
result = solution.searchRange(nums, target)
print(result)
LeetCode 第 35 题：搜索插入位置
传送门：35. 搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 1:
输入: [1,3,5,6], 5 输出: 2示例 2:
输入: [1,3,5,6], 2 输出: 1示例 3:
输入: [1,3,5,6], 7 输出: 4示例 4:
输入: [1,3,5,6], 0 输出: 0
分析：仔细分析题意，返回的是大于等于 target 的索引，有可能是最后一个。
关键之一：如果 target 比 nums 所有的数都大，则最后一个数的索引 + 1 就是候选值，因此，右边界应该是数组的长度。
关键之二：二分的逻辑一定要写对，否则会出现死循环或者数组下标越界。
Python 代码：
class Solution:
# 返回的是大于等于 target 的索引，有可能是最后一个
def searchInsert(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
size = len(nums)
if size == 0:
return 0
l = 0
r = size
while l < r:
mid = l + (r - l) // 2
if nums[mid] >= target:
r = mid
else:
assert nums[mid] < target
l = mid + 1
return l
if __name__ == '__main__':
nums = [1, 3, 5, 6]
target = 5
solution = Solution()
result = solution.searchInsert(nums, target)
print(result)
LeetCode 第 300 题：最长上升子序列
传送门：300. 最长上升子序列
给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例:
输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。说明:
- 可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
- 你算法的时间复杂度应该为 O(n2) 。
进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?
思路：自己写一个辅助数组，用二分查找完成数组的覆盖或者插入，遍历完整个输入数组，辅助数组的长度就是所求。其实这道题的一个子过程就是 LeetCode 第 35 题：搜索插入位置。这个思路用到的策略是贪心算法，技巧和二分查找。
关键：找大于等于“当前遍历的那个数”的第 1 个索引，将它替换成“当前遍历的那个数”，这样使得这个数变小，后面才有可能接一个更大的数。
注意：辅助数组不一定是一个最长上升子序列，但辅助数组的长度一定是最长上升子序列的长度。
LeetCode 第 300 题：最长上升子序列-1
LeetCode 第 300 题：最长上升子序列-2
LeetCode 第 300 题：最长上升子序列-3
Python 代码：
class Solution:
def lengthOfLIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
size = len(nums)
if size < 2:
return size
# 最长上升子序列
lis = []
for num in nums:
# 找到大于等于 target 的第 1 个数
l = 0
r = len(lis)
while l < r:
mid = l + (r - l) // 2
if lis[mid] >= num:
r = mid
else:
l = mid + 1
if l == len(lis):
lis.append(num)
else:
lis[l] = num
return len(lis)
if __name__ == '__main__':
nums = [10, 9, 2, 5, 3, 7, 101, 18]
solution = Solution()
result = solution.lengthOfLIS(nums)
print(result)
说明：这道题还可以用动态规划来完成。
（本节完）
网友评论