一、概念
二分查找每次选取区间的中间元素进行比较， 将查找的区间缩小为一半，直到找到查找的元素或者区间长度为0结束查找，思想类似分治。
二、基本特性
前提条件：
数组是有序的。
查找效率：
O（logn)
易错点：
1、循环退出的条件
2、每次查找区间一半mid的取值
3、查找区间left，right的每次更新情况
三、应用
适用于处理静态数据，没有频繁地插入、删除数据的操作。
四、局限
1、二分查找必须依赖顺序表（数组）
2、二分查找查找的必须是有序数据
3、数据量太小不适合使用二分查找
五、常考面试题：
例题1：33. 搜索旋转排序数组 https://leetcode-cn.com/problems/search-in-rotated-sorted-array/
升序排列的整数数组 nums 在预先未知的某个点上进行了旋转（例如， [0,1,2,4,5,6,7] 经旋转后可能变为 [4,5,6,7,0,1,2] ）。
请你在数组中搜索 target ，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
示例 1：
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4
示例 2：
输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1
示例 3：
输入：nums = [1], target = 0
输出：-1
思路：
思路：显然直接遍历查找是可行的，但时间复杂度是O（n）。想要加快查找速度，用二分法查找二分法查找，mid = right - left // 2，如果nums[0] < nums[mid]，说明左半部分是递增的，则在左边进行查找。否则说明右边是递增的，在右边进行查找。
时间复杂度：O（logn）
空间复杂度：O（1）
代码实现：
class Solution:
def search(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums) - 1
while left <= right:
mid = right - left // 2
if nums[mid] == target:
return mid
if nums[0] < nums[mid]:
if nums[0] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else:
if nums[mid] < target < nums[len(nums)-1]:
left = mid + 1
else:
right = mid - 1
return -1
例题2：74. 搜索二维矩阵 https://leetcode-cn.com/problems/search-a-2d-matrix/
编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。
示例 1：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true
示例 2：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false
思路：
思路1：常规遍历法，遍历二维矩阵的宽度和深度，进行数值大小比较。时间复杂度为O（m*n）， 空间复杂度为O（1）。想要提高查找效率，用二分查找。
思路2：二分法查找，时间复杂度O（logn）。
时间复杂度：O（logn）
空间复杂度：O（1）
代码实现：
# 常规查找：
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
for i in range(len(matrix)):
for j in range(len(matrix[0])):
if target == matrix[i][j]:
return True
return False
# 二分查找：
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
if not matrix:
return False
left, right = 0, len(matrix) * len(matrix[0]) - 1
while left <= right:
inde = (left + right) // 2
val = matrix[inde // len(matrix[0])][inde % len(matrix[0])]
if target == val:
return True
elif target < val:
right = inde - 1
else:
left = inde + 1
return False
例题3：367. 有效的完全平方数 https://leetcode-cn.com/problems/valid-perfect-square/
给定一个正整数 num，编写一个函数，如果 num 是一个完全平方数，则返回 True，否则返回 False。
说明：不要使用任何内置的库函数，如 sqrt。
示例 1：
输入：16
输出：True
示例 2：
输入：14
输出：False
思路：
二分法查找
如果num<2的话，则为完全平方数。如果大于2的话，开始二分法查找。right取num的一半，left取一半的一半，开始比较平方的大小，调整left和right的大小。
时间复杂度：O（logn）
空间复杂度：O（1）
代码实现：
class Solution:
def isPerfectSquare(self, num: int) -> bool:
if num < 2:
return True
left, right = 0, num // 2
while left <= right:
mid = left + (right - left) // 2
target = mid * mid
if target < num:
left = mid + 1
elif target > num:
right = mid - 1
else:
return True
return False
