二分查找是面試常考的知識(shí)點(diǎn)，其方法是在有序序列中尋找滿足特定條件的值，存在許多不同的變種，最近在刷Leetcode深有感觸，整理整理。
說明：
- 本文的二分查找變種都來自于Leetcode
- 本文不考慮整數(shù)溢出問題
普通的二分查找
- 令
left=0,right=length-1，求mid = (left+right)/2； - 對(duì)于
arr[mid] < target，arr[left,...,mid]均小于target，那么target只可能存在于arr[mid+1,...,right]； - 對(duì)于
arr[mid] > target，arr[mid,...,right]均大于target，那么target只可能存在于arr[left,...,mid-1]； - 對(duì)于
arr[mid]==target，我們已經(jīng)找到了，直接返回下標(biāo)； - 對(duì)于2和3，只要滿足
left<=right，表示總有數(shù)可以尋找。
普通二分查找
import unittest
class Solution:
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
l,h = 0, len(nums) - 1
while l<=h:
m = l + (h-l)//2
if nums[m] == target:
return m
elif nums[m] > target:
h = m - 1
else:
l = m + 1
return -1
class TestSolution(unittest.TestCase):
def setUp(self):
self.s = Solution()
def test_one(self):
input = [-1, 0, 3, 5, 9, 12]
self.assertEqual(self.s.search(input, 9), 4)
def test_two(self):
input = [-1, 0, 3, 5, 9, 12]
self.assertEqual(self.s.search(input, 2), -1)
if __name__ == "__main__":
unittest.main()
尋找target出現(xiàn)的第一個(gè)位置（數(shù)組可能存在重復(fù)數(shù)）
- 令
left=0,right=length-1，求mid = (left+right)/2； - 對(duì)于
arr[mid] < target，arr[left,...,mid]均小于target，那么target只可能存在于arr[mid+1,...,right]； - 對(duì)于
arr[mid] > target，arr[mid,...,right]均大于target，那么target只可能存在于arr[left,...,mid-1]； - 對(duì)于
arr[mid]==target，我們已經(jīng)找到了相等的值，此時(shí)可能是第一個(gè)值，也可能是中間某一個(gè)，但arr[mid+1,..,right]是不可能存在的第一個(gè)值的。因此應(yīng)該選擇right=mid； - 對(duì)于2和3，只要滿足
left<right，表示總有數(shù)可以尋找，而left==right時(shí)，已經(jīng)是最后一個(gè)數(shù)了，此時(shí)判斷該數(shù)是否是target即可。
import unittest
class Solution:
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
if len(nums) == 0:
return -1
l = 0
h = len(nums) - 1
while l < h:
m = l + (h-l)//2
if nums[m] == target:
h = m
elif nums[m] < target:
l = m + 1
else:
h = m - 1
if nums[l] != target:
return -1
return l
class TestSolution(unittest.TestCase):
def setUp(self):
self.s = Solution()
def test_one(self):
input = [-1, 0, 3, 3, 5, 9, 12]
self.assertEqual(self.s.search(input, 3), 2)
def test_two(self):
input = [-1, 0, 3, 3, 5, 9, 12]
self.assertEqual(self.s.search(input, 2), -1)
if __name__ == "__main__":
unittest.main()
尋找target最后出現(xiàn)的位置（數(shù)組可能存在重復(fù)數(shù)）
- 令
left=0,right=length-1，求mid = (left+right)/2； - 對(duì)于
arr[mid] < target，arr[left,...,mid]均小于target，那么target只可能存在于arr[mid+1,...,right]； - 對(duì)于
arr[mid] > target，arr[mid,...,right]均大于target，那么target只可能存在于arr[left,...,mid-1]； - 對(duì)于
arr[mid]==target，我們已經(jīng)找到了相等的值，此時(shí)可能是最后一個(gè)值，也可能是中間某一個(gè)，但arr[left,..,mid-1]是不可能存在的第一個(gè)值的。因此應(yīng)該選擇left=mid，但這里有個(gè)問題，就是當(dāng)left+1==right的時(shí)候，mid總等于left，此時(shí)會(huì)陷入無限循環(huán)，因此需要人工干預(yù)一下； - 對(duì)于2和3，只要滿足
left<right，表示總有數(shù)可以尋找，而left==right時(shí)，已經(jīng)是最后一個(gè)數(shù)了，此時(shí)判斷該數(shù)是否是target即可。
人工干預(yù)的兩種方式：
- 在
left == mid且arr[mid]==target的時(shí)候，表示此時(shí)left和right相鄰，而left可能是重復(fù)值的中間部分，因此先判斷right是否等于target，相等返回right，不相等就返回left。當(dāng)left == right時(shí)由于只剩一個(gè)值，只需判斷arr[left]是否等于target即可。 - 終止條件設(shè)置為
left < right - 1，這樣循環(huán)就會(huì)在l和h相鄰時(shí)終止，此時(shí)先判斷arr[right]是否等于target，不等再判斷arr[left]。
import unittest
class Solution:
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
if len(nums) == 0:
return -1
l = 0
h = len(nums) - 1
while l < h:
m = l + (h-l)//2
if nums[m] == target:
if m == l:
if nums[h] == target:
return h
else:
return l
l = m
elif nums[m] < target:
l = m + 1
else:
h = m - 1
if nums[h] != target:
return -1
return h
def search2(self, nums, target):
if len(nums) == 0:
return -1
l = 0
h = len(nums) - 1
while l < h - 1:
m = l + (h-l)//2
if nums[m] == target:
l = m
elif nums[m] < target:
l = m + 1
else:
h = m - 1
high = -1
if nums[h] == target:
high = h
elif nums[l] == target:
high = l
return high
class TestSolution(unittest.TestCase):
def setUp(self):
self.s = Solution()
def test_one(self):
input = [-1, 0, 3, 3, 5, 9, 12]
self.assertEqual(self.s.search(input, 3), 3)
self.assertEqual(self.s.search2(input, 3), 3)
def test_two(self):
input = [-1, 0, 3, 3, 5, 9, 12]
self.assertEqual(self.s.search(input, 2), -1)
self.assertEqual(self.s.search2(input, 2), -1)
if __name__ == "__main__":
unittest.main()
返回小于target的最后一個(gè)元素x的下標(biāo)（target可能不存在數(shù)組中）
- 令
left=0,right=length-1，求mid = (left+right)/2； - 對(duì)于
arr[mid] < target，arr[left,...,mid]均小于target，那么x只可能存在于arr[mid,...,right]，令left=mid； - 對(duì)于
arr[mid] > target，arr[mid,...,right]均大于x，那么x只可能存在于arr[left,...,mid-1]，令right=mid-1； - 對(duì)于
arr[mid]==target，x只可能存在于arr[left,...,mid-1]，令right=mid-1； -
當(dāng)
left+1==right的時(shí)候，mid總等于left，此時(shí)會(huì)陷入無限循環(huán)，因此需要人工干預(yù)一下，將條件設(shè)置為left < right - 1，在外層，先檢查right再檢查left；
import unittest
class Solution:
def search(self, nums, target):
if len(nums) == 0:
return -1
l = 0
h = len(nums) - 1
while l < h - 1:
m = l + (h-l)//2
if nums[m] < target:
l = m
elif nums[m] >= target:
h = m - 1
pos = -1
if nums[h] < target:
pos = h
elif nums[l] < target:
pos = l
return pos
class TestSolution(unittest.TestCase):
def setUp(self):
self.s = Solution()
def test_one(self):
input = [-1, 0, 3, 3, 5, 9, 12]
self.assertEqual(self.s.search(input, 3), 1)
def test_two(self):
input = [-1, 0, 3, 3, 5, 9, 12]
self.assertEqual(self.s.search(input, 2), 1)
def test_three(self):
input = [0]
self.assertEqual(self.s.search(input, 0), -1)
if __name__ == "__main__":
unittest.main()
返回大于target的第一個(gè)元素x的下標(biāo)（target可能不存在數(shù)組中）
- 令
left=0,right=length-1，求mid = (left+right)/2； - 對(duì)于
arr[mid] < target，arr[left,...,mid]均小于target，那么x只可能存在于arr[mid+1,...,right]，令left=mid+1； - 對(duì)于
arr[mid] > target，arr[mid,...,right]均大于x，那么x只可能存在于arr[left,...,mid]，令right=mid； - 對(duì)于
arr[mid]==target，x只可能存在于arr[mid+1,...,right]，令left=mid+1； - 判斷
arr[left]是否大于target即可
import unittest
class Solution:
def search(self, nums, target):
if len(nums) == 0:
return -1
l = 0
h = len(nums) - 1
while l < h:
m = l + (h-l)//2
if nums[m] <= target:
l = m + 1
elif nums[m] >= target:
h = m
pos = -1
if nums[l] > target:
pos = l
return pos
class TestSolution(unittest.TestCase):
def setUp(self):
self.s = Solution()
def test_one(self):
input = [-1, 0, 3, 3, 5, 9, 12]
self.assertEqual(self.s.search(input, 3), 4)
def test_two(self):
input = [-1, 0, 3, 3, 5, 9, 12]
self.assertEqual(self.s.search(input, 2), 2)
def test_three(self):
input = [0]
self.assertEqual(self.s.search(input, 0), -1)
if __name__ == "__main__":
unittest.main()
在一個(gè)旋轉(zhuǎn)數(shù)組中尋找指定target的位置（不存在重復(fù)元素）
旋轉(zhuǎn)數(shù)組有個(gè)特點(diǎn)，就是至少有一邊是有序的。
- 令
left=0,right=length-1，求mid = (left+right)/2； - 判斷
arr[left]<=arr[mid]來確定是否左邊有序(注意這邊一定要等號(hào)，因?yàn)閙id總是靠近left)，否則表示另一邊有序； - 判斷
target是否在有序的一方，如果在，則在當(dāng)前范圍內(nèi)繼續(xù)查找，否則在另一邊查找。
import unittest
class Solution:
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
if len(nums) == 0:
return -1
l,h = 0,len(nums) -1
while l <= h:
mid = l + (h-l)//2
if nums[mid] == target:
return mid
if nums[mid] >= nums[l]:
# 左邊有序
if target >= nums[l] and target < nums[mid]:
h = mid -1
else:
l = mid + 1
else:
# 右邊有序
if target > nums[mid] and target <= nums[h]:
l = mid + 1
else:
h = mid - 1
return -1
class TestSolution(unittest.TestCase):
def setUp(self):
self.s = Solution()
def test_one(self):
input = [4, 5, 6, 7, 0, 1, 2]
target = 0
self.assertEqual(self.s.search(input, target), 4)
def test_two(self):
input = [4,5,6,7,0,1,2]
target = 8
self.assertEqual(self.s.search(input, target), -1)
def test_three(self):
input = [3,1]
target = 1
self.assertEqual(self.s.search(input, target), 1)
if __name__ == "__main__":
unittest.main()
旋轉(zhuǎn)數(shù)組的最小值
- 令
left=0,right=length-1，求mid = (left+right)/2； - 判斷
arr[left]<=arr[mid]來確定是否左邊有序(注意這邊一定要等號(hào)，因?yàn)閙id總是靠近left)，否則表示另一邊有序,如果左邊和右邊皆有序，那么最小值一定是arr[left]； - 如果左邊有序，則
left=mid，如果右邊有序，則right=mid，終止條件為兩個(gè)left和right相鄰，此時(shí)left是前面子數(shù)組的最后一個(gè)，right是后面子數(shù)組的第一個(gè)，此時(shí)返回right。
注意：如果選擇旋轉(zhuǎn)數(shù)組旋轉(zhuǎn)為0，即本身有序，那么上面方法就會(huì)失效，因此在之前判斷數(shù)組本身是否有序。
import unittest
class Solution:
def findMin(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) == 0:
return -1
#數(shù)組本身有序
if nums[0] <= nums[-1]:
return nums[0]
l,h = 0,len(nums) - 1
while l < h:
m = l + (h-l)//2
if nums[l] <= nums[m]:
#左邊有序
if nums[m] <= nums[h]:
# 右邊有序
return l
else:
l = m+1
else:
#右邊有序
h = m
return l
class TestSolution(unittest.TestCase):
def setUp(self):
self.s = Solution()
def test_one(self):
input = [4,5,6,1,2,3]
self.assertEqual(self.s.findMin(input), 3)
def test_two(self):
input = [1, 2, 3]
self.assertEqual(self.s.findMin(input), 0)
if __name__ == "__main__":
unittest.main()
旋轉(zhuǎn)數(shù)組的最小值(數(shù)組包含重復(fù)值)
- 令
left=0,right=length-1，求mid = (left+right)/2； - 如果
arr[mid]==arr[left] and arr[mid] == arr[right]，那么因?yàn)闊o法判斷哪邊有序，只能轉(zhuǎn)換為順序查找； - 判斷
arr[left]<=arr[mid]來確定是否左邊有序(注意這邊一定要等號(hào)，因?yàn)閙id總是靠近left)，否則表示另一邊有序,如果左邊和右邊皆有序，那么最小值一定是arr[left]； - 如果左邊有序，則
left=mid，如果右邊有序，則right=mid，終止條件為兩個(gè)left和right相鄰，此時(shí)left是前面子數(shù)組的最后一個(gè)，right是后面子數(shù)組的第一個(gè)，此時(shí)返回right。
注意：如果選擇旋轉(zhuǎn)數(shù)組旋轉(zhuǎn)為0，即本身有序，那么上面方法就會(huì)失效，因此在之前判斷數(shù)組本身是否有序。
import unittest
class Solution:
def findMin(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) == 0:
return -1
#數(shù)組本身有序
if nums[0] <= nums[-1]:
return nums[0]
l,h = 0,len(nums) - 1
while l < h:
m = l + (h-l)//2
if nums[l] <= nums[m]:
#左邊有序
if nums[m] <= nums[h]:
# 右邊有序
return l
else:
l = m+1
else:
#右邊有序
h = m
return l
class TestSolution(unittest.TestCase):
def setUp(self):
self.s = Solution()
def test_one(self):
input = [4,5,6,1,2,3]
self.assertEqual(self.s.findMin(input), 3)
def test_two(self):
input = [1, 2, 3]
self.assertEqual(self.s.findMin(input), 0)
if __name__ == "__main__":
unittest.main()
做了以上這些題目，可以總結(jié)出以下要注意的點(diǎn)
- 解題思路：考慮初始、循環(huán)和終止過程，循環(huán)過程根據(jù)目標(biāo)值存在于哪個(gè)子數(shù)組來更改
left和right； - 如果存在使
left=mid的情況，需要干預(yù)循環(huán)結(jié)束條件，因?yàn)樵?code>left和right相鄰時(shí)，left==mid，那么如果left=mid，會(huì)導(dǎo)致每次循環(huán)無法減少候選數(shù)組，最終導(dǎo)致死循環(huán)； - 有時(shí)候需要在最外層判斷指針指向的位置是否符合條件，如循環(huán)結(jié)束條件為
l < h - 1。 - 循環(huán)數(shù)組的解題思路就是尋找有序子數(shù)組；
- 對(duì)于旋轉(zhuǎn)數(shù)組如果存在重復(fù)數(shù)導(dǎo)致無法判斷前后哪個(gè)序列為有序，那么就要轉(zhuǎn)化為順序查找。
