100道高频LeetCode算法图文题解，数组二分一写就废

　　在这个系列的博客中，我们根据LeetCode官方给出的每个题目的出现频率，整理并收录了每个类别里高频出现的题目，从简单到中等再到困难，为你提供解题技巧和最佳实践。我们将介绍常见的算法思想，如贪心算法、动态规划、回溯算法等，希望能帮助你提高算法水平，成为你进入人工智能行业敲门砖。
　　704：二分查找（难度2/频率5）
　　题目链接：https://leetcode-cn.com/problems/binary-search/
　　给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
　　示例 1:
　　输入: nums = [-1,0,3,5,9,12], target = 9
　　输出: 4
　　解释: 9 出现在 nums 中并且下标为 4
　　示例 2:
　　输入: nums = [-1,0,3,5,9,12], target = 2
　　输出: -1
　　解释: 2 不存在 nums 中因此返回 -1解题思路
　　本题提到数组为有序数组 ，同时还强调 无重复元素 ，因为一旦有重复元素，使用二分查找法返回的元素下标可能不是唯一的，这些都是使用 二分法的前提条件 ，当大家看到题目描述满足如上条件的时候，可要想一想是不是可以用二分法了。
　　大家写二分法经常写乱，主要是因为 对区间的定义没有想清楚，区间的定义就是不变量 。要不信你现在可以动手写个二分查找，一定会遇到一个问题，到底是  while(left < right)  还是 while(left <= right) ，到底是right = middle 呢，还是要right = middle - 1 呢？在二分查找的过程中，保持不变量，就是在while寻找中每一次边界的处理都要坚持根据区间的定义来操作，这就是 循环不变量 规则。
　　二分查找的区间是不断迭代的，解决上述问题就一定要遵循区间定义， 区间的定义一般为两种，左闭右闭即[left, right]，或者左闭右开即[left, right)。 第一种写法：区间左闭右闭
　　区间的定义决定了二分法的代码应该如何写，因为定义target在[left, right]区间，所以有如下两点： while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <= if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle - 1
　　例如在下列数组查找元素33，如图所示：
　　递增数组，索引为0和11
　　注意middle的计算
　　注意left的变化
　　class Solution:     def search(self, nums: List[int], target: int) -> int:         left, right = 0, len(nums) - 1  # 定义target在左闭右闭的区间里，[left, right]         while left <= right:             middle = left + (right - left) // 2             if nums[middle] > target:                 right = middle - 1  # target在左区间，所以[left, middle - 1]             elif nums[middle] < target:                 left = middle + 1  # target在右区间，所以[middle + 1, right]             else:                 return middle  # 数组中找到目标值，直接返回下标         return -1  # 未找到目标值第二种写法：区间左闭右开
　　区间左闭右开，也就是[left, right) ，那么二分法的边界处理方式则截然不同。
　　有如下两点： while (left < right)，这里使用 < ,因为left == right在区间[left, right)是没有意义的； if (nums[middle] > target) right 更新为 middle，因为当前nums[middle]不等于target，去左区间继续寻找，而寻找区间是左闭右开区间，所以right更新为middle；
　　比如在数组：1,2,3,4,7,9,10中查找元素2，如图所示：
　　class Solution:     def search(self, nums: List[int], target: int) -> int:         left, right = 0, len(nums)  # 定义target在左闭右开的区间里，即：[left, right)         while left < right:  # 因为left == right的时候，在[left, right)是无效的空间，所以使用 <             middle = left + (right - left) // 2             if nums[middle] > target:                 right = middle  # target 在左区间，在[left, middle)中             elif nums[middle] < target:                 left = middle + 1  # target 在右区间，在[middle + 1, right)中             else:                 return middle  # 数组中找到目标值，直接返回下标         return -1  # 未找到目标值题目总结
　　二分法是非常重要的基础算法，理解清楚区间的定义，从而更准确的处理边界情况，其时间复杂度为（O (log2n )），再通过一个动图让你加深对二分法的理解。
　　相关题目推荐35.搜索插入位置 34. 在排序数组中查找元素的第一个和最后一个位置 69. x 的平方根 367.有效的完全平方数