二分查找也称折半查找（Binary Search），是一种在有序数组中查找某一特定元素的搜索算法。我们可以从定义可知，运用二分搜索的前提是数组必须是有序的，这里需要注意的是，我们的输入不一定是数组，也可以是数组中某一区间的起始位置和终止位置
0 经典二分法
中间位置的计算：
mid=left+(right-left)//2或者使用位运算mid=left + ((right - left) >> 1)，注意不能使用 （left + right ）/ 2,否则有可能会导致溢出。
计算思路：
二分查找的执行过程如下
1.从已经排好序的数组或区间中，取出中间位置的元素，将其与我们的目标值进行比较，判断是否相等，如果相等
则返回。
2.如果 nums[mid] 和 target 不相等，则对 nums[mid] 和 target 值进行比较大小，通过比较结果决定是从 mid
的左半部分还是右半部分继续搜索。如果 target > nums[mid] 则右半区间继续进行搜索，即 left = mid + 1; 若
target < nums[mid] 则在左半区间继续进行搜索，即 right = mid -1；
注意事项：
1.while (left < = right) { } 注意括号内为 left <= right ,而不是 left < right ，如果我们设置条件为 left < right 则当我们执行到最后一步时，则我们的 left 和 right 重叠时，则会跳出循环，返回 -1，区间内不存在该元素，但是不是这样的，我们的 left 和 right 此时指向的就是我们的目标元素 ，但是此时 left = right 跳出循环
代码：
（1）非递归写法
def binarySearch(arr,target,left,right):
while(left<=right):
mid=left + (right - left)//2
if(arr[mid]==target):
return mid
elif(target>arr[mid]):
left=mid+1
elif(target<arr[mid]):
right=mid-1
return -1
if __name__ == '__main__':
arr=[1,2,3,6,7,8,11,13,15,16]
res=binarySearch(arr,8,0,9)
print(res)(2)递归写法
def binarySearchbyRecursion(arr,target,left,right):
if(left<=right):#记得加这个判断条件
mid=left+(right - left)//2
if(arr[mid]==target):
return mid
elif(target>arr[mid]):
return binarySearchbyRecursion(arr,target,mid+1,right)#一定要记得Return 不然最后都是执行return -1，返回-1
elif(target<arr[mid]):
return binarySearchbyRecursion(arr,target,left,mid-1)#一定要记得Return 不然最后都是执行return -1，返回-1
return -1变形1 无重复 有序
1.1 LTD35 搜索插入位置
题目描述
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 1:
输入: [1,3,5,6], 5
输出: 2
示例 2:
输入: [1,3,5,6], 2
输出: 1
解题：
这个题目完全就和咱们的二分查找一样，只不过有了一点改写，那就是将咱们的返回值改成了 left或者mid+1，具体实现过程见下图
def binarySearch(arr,target,left,right):
while(left<=right):#记得加这个判断条件
mid=left + (right - left) //2
if(arr[mid]==target):
return mid
elif(target>arr[mid]):
left=mid+1
elif(target<arr[mid]):
right=mid-1
return left#或者为mid+11.2 剑指 Offer 53 - II. 0～n-1中缺失的数字
题目描述：
一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
示例 1:
输入: [0,1,3]
输出: 2示例 2:
输入: [0]
输出: 1解题思路
与leetcode35搜索插入位置有点子像，这里把Target想象成mid
在数组中找到mid！=nums[mid]，并返回mid插入数组中的位置。
class Solution(object):
def missingNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
left,right=0,len(nums)-1
while(left<=right):
mid=left+(right-left)//2
if(nums[mid]!=mid):
right=mid-1
else:
left=mid+1
return left1.3 LTD69. x 的平方根
题目描述：
实现 int sqrt(int x) 函数:计算并返回 x 的平方根，其中 x 是非负整数。由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例 1:
输入: 4
输出: 2示例 2:
输入: 8
输出: 2
说明: 8 的平方根是 2.82842...,
由于返回类型是整数，小数部分将被舍去。解题思路
用二分法判断，初始区间为[0,x]，然后不断的找最大的mid使得mid*mid<=即可，即ans=mid。
代码
class Solution(object):
def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
left,right,ans=0,x,-1
while left<=right:
mid=left+(right-left)//2
if mid*mid<=x:
ans=mid
left=mid+1
else:
right=mid-1
return ans1.4 LTD50. Pow(x, n)
题目描述
实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。
示例 1：
输入：x = 2.00000, n = 10
输出：1024.00000More:
变形2 有序数组 但是有重复值
2.1 LTD 34在排序数组中查找元素的第一个和最后一个位置
题目描述
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
示例 2：
输入：nums = [], target = 0
输出：[-1,-1]
思路1：
我们只需在这段代码中修改即可，nums[mid] == target 时则返回，nums[mid] < target 时则移动左指针，在右区间进行查找， nums[mid] > target时则移动右指针，在左区间内进行查找。
计算下边界时，当 target <= nums[mid] 时，right = mid -1；target > nums[mid] 时，left = mid + 1；
计算上边界时，当 target < nums[mid] 时，right = mid -1; target >= nums[mid] 时 left = mid + 1;刚好和计算下边界时条件相反，返回right。
代码：
def binarySearchbyLt32(arr,target,left,right):
upper=upperBound(arr,target,left,right)
lower=lowerBound(arr,target,left,right)
if(lower>upper):#不存在的情况
return [-1,-1]
else:
return [lower,upper]
#计算下边界
def lowerBound(arr,target,left,right):
while(left<=right):#记得加这个判断条件
mid=left + (right - left) //2
if(target>arr[mid]):
left=mid+1
elif(target<=arr[mid]):#相等依然往左边，移动右指针往左
right=mid-1
return left#返回left
#计算上边界
def upperBound(arr,target,left,right):
while(left<=right):#记得加这个判断条件
mid=left + (right - left) //2
if(target>=arr[mid]):#相等依然往右边，移动左指针往右
left=mid+1
elif(target<arr[mid]):
right=mid-1
return right思路2：推荐，复用代码
左边界：返回left，即为第一个等于target的索引
右边界：即为taget+1的左边界-1：最后一个等于target的索引=第一个等于target+1的索引-1
class Solution(object):
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
def leftBound(nums,target):
left,right=0,len(nums)-1
#计算左边界
while(left<=right):
mid=left+(right-left)//2
if(target<=nums[mid]):
right=mid-1
elif(target>nums[mid]):
left=mid+1
return left
left=leftBound(nums,target)
right=leftBound(nums,target+1)-1
if(right<left):
return [-1,-1]
else:
return [left,right]2.2 找出第一个大于目标元素的索引
题目描述：
找出第一个大于目标元素的索引，若找不到目标元素，则返回-1
1.数组包含目标元素，找出在他后面的第一个元素
2.目标元素不在数组中，数组内的部分元素大于它，此时我们需要返回第一个大于他的元素
3.目标元素不在数组中，且数组中的所有元素都大于它，那么我们此时返回数组的第一个元素即可
4.目标元素不在数组中，且数组中的所有元素都小于它，那么我们此时没有查询到，返回 -1 即可。
示例 1：
输入：nums =[1,3,5,5,6,6,8,9,11], target = 5
输出：4
示例 2：
输入：nums =[1,3,5,5,6,6,8,9,11], target = 4
输出：-1
解题思路：
在leetcode 34题目基础上，找到右边界+1即可。
代码：
def binarySearchbyFirstUpIndex(arr,target,left,right):
while(left<=right):#记得加这个判断条件
mid=left + (right - left) //2
if(target>=arr[mid]):#相等依然往右边
left=mid+1
elif(target<arr[mid]):
if(mid==0|target>arr[mid-1]):
return mid
else:
right=mid-1
return -12.3 找出最后一个小于目标元素的索引
题目描述：
nums = {1,3,5,5,6,6,8,9,11} target = 7
解题思路：
变形3 不完全有序 不含重复值
3.1 LTD33 搜索旋转排序数组—查找目标元素（不含重复元素）
题目描述：
整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 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解题思路：
当我们将数组从中间分开成左右两部分的时候，首先需要判断mid的位置；然后判断target的位置；所以2x2=4,会有四种组合
第一步：判断mid的位置：
可以发现的是，我们将数组从中间分开成左右两部分的时候，一定有一半的数组是有序的。拿示例来看，我们从 6 这个位置分开以后数组变成了 [4, 5, 6] 和 [7, 0, 1, 2] 两个部分，其中左边 [4, 5, 6] 这个部分的数组是有序的，因为有序数组 ，我们就可以用到前面的二分查找。所以mid的位置就是两种情况：
（1）mid的左边是有序的，即[left,mid]有序，[mid,right]无序。我们可以使用num[mid]与num[left]做比较，可以得出当nums[mid]>=nums[left]时候，mid的左边是有序数组。
第二步：判断target的位置
前提条件：mid的左边是有序数组；现在我们来判断target的位置
a.当target落在mid的左边区域（target<nums[mid] and target>=nums[left]），即有序的，则right=mid-1;往左查找。这时候注意target需要包含=num[left]的情况。
b.当target落在mid的右边无序区域，需要往右查找：left=mid+1
（2）mid的右边是有序的，即[left,mid]无序，[mid,right]有序。可以得出当nums[mid]<nums[left]时候，mid的右边是有序数组。其实我们只分析一种情况，另外一种可以直接用else。
第二步：判断target的位置
前提条件：mid的右边是有序数组；现在我们来判断target的位置
a.当target落在mid的右边有序区域（target>nums[mid] and target<nums[left]），则left=mid+1;往右查找。其实这个条件与（1）.a的条件是相反的。
b.当target落在mid的左边无序区域，需要往左查找：right=mid-1
代码
def BinarySearchIndisOrder(nums, target):
left,right=0,len(nums)-1
while(left<=right):
mid=left+(right-left)//2
#step1 判断mid的位置
if(nums[mid]==target):
return mid
if(nums[mid]>=nums[left]):#[left,mid]有序
#step2 判断target的位置
if(target<nums[mid] and target>=nums[left]): #target在左边
right=mid-1
else:
left=mid+1
else:#[left,mid]无序，[mid,right]有序
if(target>nums[mid] and target<nums[left]):#target在右边
left=mid+1
else:
right=mid-1
return -1#没有查到复杂度分析
时间复杂度：O(logn)，其中 nn 为nums 数组的大小。整个算法时间复杂度即为二分查找的时间复杂度 O(log n)O(logn)。
空间复杂度： O(1)O(1) 。我们只需要常数级别的空间存放变量。
3.2 LTD153 寻找旋转排序数组中的最小值 不含重复值
题目描述：
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。
给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
示例 1：
输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。
示例 2：
输入：nums = [11,13,15,17]
输出：11
解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。
解题思路
寻找最小值，只需要比较mid和right的值即可，原因见为什么比较右边界。
（1）当中间值比右边值小的时候（nums[mid]<nums[right]），则往左边找，因为此时nums[mid]有可能是最小值，因此right=mid而不是right=mid-1,因为mid-1会错过最小值nums[mid]
（2）当中间值比右边大的时候（nums[mid]>nums[right]），则往右找，此时nums[mid]肯定不是最小值，所以left=left+1;
（3）因为是无重复数组，所以不存在nums[mid]==nums[right]
代码
def findMin(nums):
"""
:type nums: List[int]
:rtype: int
"""
left,right=0,len(nums)-1
while left<right:
mid=left+(right-left)//2
if nums[mid]<nums[right]:#[left,mid]有序
# 如果中间值小于最大值，则最大值减小
# 疑问：为什么
# high = mid;
# 而不是
# high = mid - 1;
# 解答：{4, 5, 1, 2, 3}，如果high = mid - 1，则丢失了最小值1
right=mid#如果mid是最小值 则right=mid-1会错过最小值
else:
# 如果中间值大于最大值，则最小值变大
#疑问：为什么
# low = mid + 1;
# 而不是
# low = mid;
# 解答：{4, 5, 6, 1, 2, 3}，nums[mid] = 6，low = mid + 1, 刚好nums[low] = 1
#继续疑问：上边的解释太牵强了，难道没有可能low = mid + 1, 正好错过了最小值
#继续解答：不会错过!!! 因为nums[mid]>=nums[right],所以nums[mid]一定不是最小值
left=mid+1
return nums[left]复杂度分析
log(n)
变形4 不完全有序 含重复值
4.1 LTD81搜索旋转排序数组 II 含重复值
题目描述：
已知存在一个按非降序排列的整数数组 nums ，数组中的值不必互不相同。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转 ，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。
给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。
示例 1：
输入：nums = [2,5,6,0,0,1,2], target = 0
输出：true示例 2：
输入：nums = [2,5,6,0,0,1,2], target = 3
输出：false解题思路：
这个题目是3.1的变形，对于数组中有重复元素的情况，二分查找时可能会有a[left]=a[mid]=a[right]，此时无法判断哪个区间是有序的。
例如nums=[3,1,2,3,3,3,3]，target=2，首次二分时无法判断区间 [0,3][0,3] 和区间 [4,6][4,6] 哪个是有序的。
对于这种情况，我们只能将当前二分区间的左边界加一，右边界减一，然后在新区间上继续二分查找。
代码
class Solution(object):
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
left,right=0,len(nums)-1
while(left<=right):
mid=left+(right-left)//2
#step1 判断mid的位置
if(nums[mid]==target):
return True
if (nums[mid]==nums[left] and nums[mid]==nums[right]):#去掉重复值
left=left+1
right=right-1
elif(nums[mid]>=nums[left]):#[left,mid]有序 ##注意这里要用elif：因为去掉重复值后开启新的判断，即新的left,right
#step2 判断target的位置
if(target<nums[mid] and target>=nums[left]): #target在左边
right=mid-1
else:
left=mid+1
else:#[left,mid]无序，[mid,right]有序
if(target>nums[mid] and target<nums[left]):#target在右边
left=mid+1
else:
right=mid-1
return False#没有查到复杂的分析
4.2 LTD154. 寻找旋转排序数组中的最小值 II 含重复值
题目描述：
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,4,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,4]
若旋转 7 次，则可以得到 [0,1,4,4,5,6,7]
注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。
给你一个可能存在 重复 元素值的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
示例 1：
输入：nums = [1,3,5]
输出：1
示例 2：
输入：nums = [2,2,2,0,1]
输出：0
解题思路
在3.2的基础上 判断考虑（3）nums[mid]==nums[right]的情况：
（3）当nums[mid]==nums[right]时候，我们无法判断最小值在左边还是右边，此时舍弃num[right]即可。
代码
class Solution(object):
def findMin(self,nums):
"""
:type nums: List[int]
:rtype: int
"""
left,right=0,len(nums)-1
while left<right:
mid=left+(right-left)//2
if nums[mid]<nums[right]:#[left,mid]有序
# 如果中间值小于最大值，则最大值减小
# 疑问：为什么
# high = mid;
# 而不是
# high = mid - 1;
# 解答：{4, 5, 1, 2, 3}，如果high = mid - 1，则丢失了最小值1
right=mid#如果mid是最小值 则right=mid-1会错过最小值
elif nums[mid]>nums[right]:
# 如果中间值大于最大值，则最小值变大
#疑问：为什么
# low = mid + 1;
# 而不是
# low = mid;
# 解答：{4, 5, 6, 1, 2, 3}，nums[mid] = 6，low = mid + 1, 刚好nums[low] = 1
#继续疑问：上边的解释太牵强了，难道没有可能low = mid + 1, 正好错过了最小值
#继续解答：不会错过!!! 因为nums[mid]>=nums[right],所以nums[mid]一定不是最小值
left=mid+1
else:#nums[mid]==nums[right]
right=right-1
return nums[left]