二分查找是面试常考的知识点，其方法是在有序序列中寻找满足特定条件的值，存在许多不同的变种，最近在刷Leetcode深有感触，整理整理。
说明：
- 本文的二分查找变种都来自于Leetcode
- 本文不考虑整数溢出问题
普通的二分查找
- 令
left=0,right=length-1，求mid = (left+right)/2； - 对于
arr[mid] < target，arr[left,...,mid]均小于target，那么target只可能存在于arr[mid+1,...,right]； - 对于
arr[mid] > target，arr[mid,...,right]均大于target，那么target只可能存在于arr[left,...,mid-1]； - 对于
arr[mid]==target，我们已经找到了，直接返回下标； - 对于2和3，只要满足
left<=right，表示总有数可以寻找。
普通二分查找
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出现的第一个位置（数组可能存在重复数）
- 令
left=0,right=length-1，求mid = (left+right)/2； - 对于
arr[mid] < target，arr[left,...,mid]均小于target，那么target只可能存在于arr[mid+1,...,right]； - 对于
arr[mid] > target，arr[mid,...,right]均大于target，那么target只可能存在于arr[left,...,mid-1]； - 对于
arr[mid]==target，我们已经找到了相等的值，此时可能是第一个值，也可能是中间某一个，但arr[mid+1,..,right]是不可能存在的第一个值的。因此应该选择right=mid； - 对于2和3，只要满足
left<right，表示总有数可以寻找，而left==right时，已经是最后一个数了，此时判断该数是否是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最后出现的位置（数组可能存在重复数）
- 令
left=0,right=length-1，求mid = (left+right)/2； - 对于
arr[mid] < target，arr[left,...,mid]均小于target，那么target只可能存在于arr[mid+1,...,right]； - 对于
arr[mid] > target，arr[mid,...,right]均大于target，那么target只可能存在于arr[left,...,mid-1]； - 对于
arr[mid]==target，我们已经找到了相等的值，此时可能是最后一个值，也可能是中间某一个，但arr[left,..,mid-1]是不可能存在的第一个值的。因此应该选择left=mid，但这里有个问题，就是当left+1==right的时候，mid总等于left，此时会陷入无限循环，因此需要人工干预一下； - 对于2和3，只要满足
left<right，表示总有数可以寻找，而left==right时，已经是最后一个数了，此时判断该数是否是target即可。
人工干预的两种方式：
- 在
left == mid且arr[mid]==target的时候，表示此时left和right相邻，而left可能是重复值的中间部分，因此先判断right是否等于target，相等返回right，不相等就返回left。当left == right时由于只剩一个值，只需判断arr[left]是否等于target即可。 - 终止条件设置为
left < right - 1，这样循环就会在l和h相邻时终止，此时先判断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的最后一个元素x的下标（target可能不存在数组中）
- 令
left=0,right=length-1，求mid = (left+right)/2； - 对于
arr[mid] < target，arr[left,...,mid]均小于target，那么x只可能存在于arr[mid,...,right]，令left=mid； - 对于
arr[mid] > target，arr[mid,...,right]均大于x，那么x只可能存在于arr[left,...,mid-1]，令right=mid-1； - 对于
arr[mid]==target，x只可能存在于arr[left,...,mid-1]，令right=mid-1； -
当
left+1==right的时候，mid总等于left，此时会陷入无限循环，因此需要人工干预一下，将条件设置为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的第一个元素x的下标（target可能不存在数组中）
- 令
left=0,right=length-1，求mid = (left+right)/2； - 对于
arr[mid] < target，arr[left,...,mid]均小于target，那么x只可能存在于arr[mid+1,...,right]，令left=mid+1； - 对于
arr[mid] > target，arr[mid,...,right]均大于x，那么x只可能存在于arr[left,...,mid]，令right=mid； - 对于
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()
在一个旋转数组中寻找指定target的位置（不存在重复元素）
旋转数组有个特点，就是至少有一边是有序的。
- 令
left=0,right=length-1，求mid = (left+right)/2； - 判断
arr[left]<=arr[mid]来确定是否左边有序(注意这边一定要等号，因为mid总是靠近left)，否则表示另一边有序； - 判断
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,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()
旋转数组的最小值
- 令
left=0,right=length-1，求mid = (left+right)/2； - 判断
arr[left]<=arr[mid]来确定是否左边有序(注意这边一定要等号，因为mid总是靠近left)，否则表示另一边有序,如果左边和右边皆有序，那么最小值一定是arr[left]； - 如果左边有序，则
left=mid，如果右边有序，则right=mid，终止条件为两个left和right相邻，此时left是前面子数组的最后一个，right是后面子数组的第一个，此时返回right。
注意：如果选择旋转数组旋转为0，即本身有序，那么上面方法就会失效，因此在之前判断数组本身是否有序。
import unittest
class Solution:
def findMin(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) == 0:
return -1
#数组本身有序
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()
旋转数组的最小值(数组包含重复值)
- 令
left=0,right=length-1，求mid = (left+right)/2； - 如果
arr[mid]==arr[left] and arr[mid] == arr[right]，那么因为无法判断哪边有序，只能转换为顺序查找； - 判断
arr[left]<=arr[mid]来确定是否左边有序(注意这边一定要等号，因为mid总是靠近left)，否则表示另一边有序,如果左边和右边皆有序，那么最小值一定是arr[left]； - 如果左边有序，则
left=mid，如果右边有序，则right=mid，终止条件为两个left和right相邻，此时left是前面子数组的最后一个，right是后面子数组的第一个，此时返回right。
注意：如果选择旋转数组旋转为0，即本身有序，那么上面方法就会失效，因此在之前判断数组本身是否有序。
import unittest
class Solution:
def findMin(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) == 0:
return -1
#数组本身有序
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()
做了以上这些题目，可以总结出以下要注意的点
- 解题思路：考虑初始、循环和终止过程，循环过程根据目标值存在于哪个子数组来更改
left和right； - 如果存在使
left=mid的情况，需要干预循环结束条件，因为在left和right相邻时，left==mid，那么如果left=mid，会导致每次循环无法减少候选数组，最终导致死循环； - 有时候需要在最外层判断指针指向的位置是否符合条件，如循环结束条件为
l < h - 1。 - 循环数组的解题思路就是寻找有序子数组；
- 对于旋转数组如果存在重复数导致无法判断前后哪个序列为有序，那么就要转化为顺序查找。
