二分法模板方法

二分法也有其套路，通常定义首尾双指针，然后通过取得中间位置mid进行条件判断，从而缩短查找的范围。

实例分步解析

下面将以找到排序数组中target第一次出现的位置为例，分步解析二分法。

nums= [1,2,2,3,3,3,4,4,5], target=4, return 6

确定返回值类型和查找范围

返回的是target在数组中的位置，即index。
查找范围：[start=0, end=len(nums)-1]

确定二分条件

由于找第一次出现，当nums[mid] == target时，仍要向左边缩减。
nums[mid] < target ? 说明target在右边，取右半边。

模板背诵

• start + 1 < end （相邻就退出）
  将此作为退出条件好处是保证start和end不重合，避免了花费大量时间来思路start=end的情况，也避免了二分缩减时程序陷入死循环。
• mid = start + (end - start) / 2
  不直接将start和end相加，防止大数溢出。
• A[mid] ==? < ? > (判断)
  二分判断时宁愿分三种情况考虑，避免思维不清晰时进行错误的缩减。
• A[start],A[end]? target (double check)
  由于start和end相邻就退出，最后需要对所得的两个指针进行二重判断。如果题目求第一次出现或最后一次出现的位置时，而nums[start]、nums[end]可能都和target相等，双重判断然后根据题目需要返回对应的位置。

模块小结

##### 确定返回值类型和查找范围 #####
start = 0
end = n - 1##### 二分主题 #####
# 相邻就退出 #
while(start + 1 < end):# 中位数表示 #mid = start + (end - start) // 2# 三次condition判断 #if nums[mid] == target:end = midelif nums[mid] > target:end = midelse:start = mid# double check #
if nums[start] == target:return start
if nums[end] == target:return end

完整代码

class Solution:def findFirstIndex(self, nums, target):n = len(nums)if (nums is None or n == 0):return -1start = 0end = n - 1while(start + 1 < end):# 相邻就退出mid = start + (end - start) // 2if nums[mid] == target:end = midelif nums[mid] > target:end = midelse:start = midif nums[start] == target:return startif nums[end] == target:return endreturn -1