二分查找法
說明：二分查找法在代碼實(shí)現(xiàn)上有模板方法，一定要掌握。
1、二分查找法的使用前提：數(shù)組一定要是排好序的，如果數(shù)組不是排好序的，二分查找法便不能使用。
2、實(shí)現(xiàn)二分查找法的關(guān)鍵之處：維護(hù)循環(huán)不變量的定義。如果修改了區(qū)間邊界的定義，算法得相應(yīng)改變。
技巧：可以使用小數(shù)據(jù)量進(jìn)行測(cè)試。
下面給出的問題不是標(biāo)準(zhǔn)的二分查找問題，但是可以用二分查找的思想來解決，稍微要繞一點(diǎn)彎子。其中，第 300 題要用到第 35 題。
LeetCode 第 34 題：在排序數(shù)組中查找元素的第一個(gè)和最后一個(gè)位置
傳送門：34. 在排序數(shù)組中查找元素的第一個(gè)和最后一個(gè)位置。
給定一個(gè)按照升序排列的整數(shù)數(shù)組
nums，和一個(gè)目標(biāo)值target。找出給定目標(biāo)值在數(shù)組中的開始位置和結(jié)束位置。你的算法時(shí)間復(fù)雜度必須是 O(log n) 級(jí)別。
如果數(shù)組中不存在目標(biāo)值，返回
[-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]
思路：使用二分查找，我使用的是二分查找法我認(rèn)為最好用的模板寫法。
1、循環(huán)可以繼續(xù)的條件是 l < r，這樣退出循環(huán)的時(shí)候 l == r 成立，因此就不用糾結(jié)返回 l 還是 r 了；
不過要特別注意一點(diǎn)：我們是通過夾逼的方式把搜索的范圍逼到一個(gè)點(diǎn)，那么這個(gè)點(diǎn)是不是符合要求還要單獨(dú)做判斷。
2、循環(huán)體比較簡(jiǎn)單，真正地做到了“二分”，即“寫兩個(gè)分支”作判斷，只要分支條件寫正確，其中一個(gè)分支一定可以排除掉中點(diǎn)，而另一個(gè)分支則保留了中點(diǎn)；
3、取“中點(diǎn)”的操作有 2 種，根據(jù)循環(huán)體的收縮情況，采用合適的中點(diǎn)方法，這一點(diǎn)很重要，否則會(huì)出現(xiàn)死循環(huán)。
（1）mid = l + (r - l) // 2，特點(diǎn)：在只有兩個(gè)數(shù)的時(shí)候，靠近左邊。
（2）mid = l + (r - l + 1) // 2，特點(diǎn)：在只有兩個(gè)數(shù)的時(shí)候，靠近右邊。
例如：循環(huán)體是 l = mid + 1 和 r = mid 的時(shí)候，表示左端點(diǎn)不斷右移，則選擇（1），否則會(huì)出現(xiàn)死循環(huán)；
循環(huán)體是 l = mid 和 r = mid - 1 的時(shí)候，表示右端點(diǎn)不斷左移，則選擇（2），否則會(huì)出現(xiàn)死循環(huán)。
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 個(gè)元素的索引
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
# 最后還要單獨(dú)判斷一下
if nums[l] != target:
return -1
return l
def __find_up_bound(self, nums, target):
# 找到大于等于 target 的最后 1 個(gè)元素的索引
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
# 最后還要單獨(dú)判斷一下
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. 搜索插入位置
給定一個(gè)排序數(shù)組和一個(gè)目標(biāo)值，在數(shù)組中找到目標(biāo)值，并返回其索引。如果目標(biāo)值不存在于數(shù)組中，返回它將會(huì)被按順序插入的位置。
你可以假設(shè)數(shù)組中無重復(fù)元素。
示例 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
分析：仔細(xì)分析題意，返回的是大于等于 target 的索引，有可能是最后一個(gè)。
關(guān)鍵之一：如果 target 比 nums 所有的數(shù)都大，則最后一個(gè)數(shù)的索引 + 1 就是候選值，因此，右邊界應(yīng)該是數(shù)組的長(zhǎng)度。
關(guān)鍵之二：二分的邏輯一定要寫對(duì)，否則會(huì)出現(xiàn)死循環(huán)或者數(shù)組下標(biāo)越界。
Python 代碼：
class Solution:
# 返回的是大于等于 target 的索引，有可能是最后一個(gè)
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 題：最長(zhǎng)上升子序列
給定一個(gè)無序的整數(shù)數(shù)組，找到其中最長(zhǎng)上升子序列的長(zhǎng)度。
示例:
輸入: [10,9,2,5,3,7,101,18] 輸出: 4 解釋: 最長(zhǎng)的上升子序列是 [2,3,7,101]，它的長(zhǎng)度是 4。說明:
- 可能會(huì)有多種最長(zhǎng)上升子序列的組合，你只需要輸出對(duì)應(yīng)的長(zhǎng)度即可。
- 你算法的時(shí)間復(fù)雜度應(yīng)該為 O(n2) 。
進(jìn)階: 你能將算法的時(shí)間復(fù)雜度降低到 O(n log n) 嗎?
思路：自己寫一個(gè)輔助數(shù)組，用二分查找完成數(shù)組的覆蓋或者插入，遍歷完整個(gè)輸入數(shù)組，輔助數(shù)組的長(zhǎng)度就是所求。其實(shí)這道題的一個(gè)子過程就是 LeetCode 第 35 題：搜索插入位置。這個(gè)思路用到的策略是貪心算法，技巧和二分查找。
關(guān)鍵：找大于等于“當(dāng)前遍歷的那個(gè)數(shù)”的第 1 個(gè)索引，將它替換成“當(dāng)前遍歷的那個(gè)數(shù)”，這樣使得這個(gè)數(shù)變小，后面才有可能接一個(gè)更大的數(shù)。
注意：輔助數(shù)組不一定是一個(gè)最長(zhǎng)上升子序列，但輔助數(shù)組的長(zhǎng)度一定是最長(zhǎng)上升子序列的長(zhǎng)度。
Python 代碼：
class Solution:
def lengthOfLIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
size = len(nums)
if size < 2:
return size
# 最長(zhǎng)上升子序列
lis = []
for num in nums:
# 找到大于等于 target 的第 1 個(gè)數(shù)
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)
說明：這道題還可以用動(dòng)態(tài)規(guī)劃來完成。
（本節(jié)完）
