二分查找的秘密
二分查找法，其实也叫“折半查找”，是一种效率较高的查找方法。同时它也告诉了我们使用的条件，首先线性表需要是有序的，并且不能有重复元素，这就是使用它的前提条件。看到可能会觉得好像很容易呀，虽然我们判断是否使用二分查找不难，但是我们在实际用它的使用却会感到麻烦不小，为什么呢？
因为我们需要考虑边界条件，由于我们很多时候对区间的定义没有想清楚，区间的定义就是不变量。要在二分查找的过程中，保持不变量，就是在while寻找中每一次边界的处理都要坚持根据区间的定义来操作，这就是循环不变量规则。
模版写法
前言： 模版不一定就是照抄，理解模版基本就能理解方法思路啦
我们能常见到的有什么区间左闭右闭法，区间左闭右开法，这里我们不强调使用什么方法，总的都是一个原则，那就是能够保证在二分查找过程中，保持不变量；自己比较习惯于用左闭右闭法，也就是[left, right]
区间的定义这就决定了二分法的代码应该如何写，因为定义target在[left, right]区间，所以有如下两点：
while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <=
if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle - 1
如果用左闭右开法的话也是类似的，只不过left<right，因为left == right在区间[left, right)是没有意义的，所以大家注意怎么去对区间进行定义就可以啦
代码如下：
class Solution:
def search(self, nums: List[int], target: int) -> int:
#1.定义区间变量left， right
left, right = 0, len(nums) - 1
#保证循环不变量，每一次的边界处理都是根据区间操作的
while left <= right:
#折半取中间值middle
middle = (left + right) // 2
#如果中间值小于了目标值，则取右半区，由于middle绝不会等于target，所有left等于middle+1
if nums[middle] < target:
left = middle + 1
#如果大于的话，取左半区，同样因为右半区值有意义，所以需要middle-1
elif nums[middle] > target:
right = middle - 1
#如果等于，则返回middle
else:
return middle
return -1
开始做题
69.x的平方
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。 由于返回类型是整数，结果只保留整数部分 ，小数部分将被舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1： 输入：x = 4 输出：2
示例 2： 输入：x = 8 输出：2
解释：8 的算术平方根是 2.82842…, 由于返回类型是整数，小数
代码如下：
class Solution:
def mySqrt(self, x: int) -> int:
left, right = 0, x
ans = -1
while left <= right:
middle = (right - left) // 2 + left
if middle * middle <= x:
ans = middle
left = middle + 1
else:
right = middle - 1
return ans
34.在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
示例 2：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
代码如下：
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
# 两次二分查找
# 取起始下标
left, right = 0, len(nums) - 1
while left < right:
mid = (left + right) // 2
if nums[mid] >= target:
right = mid
else:
left = mid + 1
# 数组不存在或者目标值不在数组中
if not nums or nums[left] != target:
return [-1, -1]
# 取结束下标
a, b = left, len(nums) - 1
while a < b:
mid = (a + b + 1) // 2
if nums[mid] <= target:
a = mid
else:
b = mid - 1
return [left, a]
