二分查找：
二分法写法： 二分法的写法共分两种分别是：1.定义target在左闭右闭区间 2.定义target在左闭右开区间。
方法1. 定义target在左闭右闭区间，即[left, right]
1.while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <=。
2.if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle – 1。
方法2. 定义target在左闭右闭区间，即[left, right)
1.while (left < right)，这里使用 < ,因为left == right在区间[left, right)是没有意义的。
2.if (nums[middle] > target) right 更新为 middle，因为当前nums[middle]不等于target，去左区间继续寻找，而寻找区间是左闭右开区间，所以right更新为middle，即：下一个查询区间不会去比较nums[middle]。
二分法力扣相关题目： 35.搜索插入位置
34.在排序数组中查找元素的第一个和最后一个位置
69.x 的平方根
367.有效的完全平方数
答案与解析：
35.搜索插入位置
题目：给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。解析 要在数组中插入目标值总共有四种情况：
请必须使用时间复杂度为 O(log n) 的算法。
1.目标值在数组所有元素之前
2.目标值等于数组中某一个元素
3.目标值插入数组中的位置
4.目标值在数组所有元素之后
文章图片
python 代码 方法1
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
left, right=0, len(nums)-1#左闭右闭区间while left <= right:
middle=left+(right-left)//2
if nums[middle]>target:
right=middle-1
elif nums[middle]方法2：
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
left, right=0, len(nums)#左闭右开区间
while left < right:
middle = left+(right-left)//2
if nums[middle]>target:
right=middle
elif nums[middle]34.在排序数组中查找元素的第一个和最后一个位置
题目：给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。解析 寻找target在数组里的左右边界，有如下三种情况：
如果数组中不存在目标值 target，返回 [-1, -1]。
情况一：target 在数组范围的右边或者左边，例如数组{3, 4, 5}，target为2或者数组{3, 4, 5},target为6，此时应该返回{-1, -1}
情况二：target 在数组范围中，且数组中不存在target，例如数组{3,6,7},target为5，此时应该返回{-1, -1}
情况三：target 在数组范围中，且数组中存在target，例如数组{3,6,7},target为6，此时应该返回{1, 1}
python 代码 方法1：
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
def getRightBoder(nums,target):
left, right = 0, len(nums)-1
rightboder=-2
while left <= right:
middle = left+(right-left)//2
if nums[middle]>target:
right=middle-1
else:
left=middle+1
rightboder=leftreturn rightboderdef getLeftBoder(nums,target):
left, right = 0, len(nums)-1
leftboder=-2
while left <= right:
middle = left+(right-left)//2
if nums[middle]>=target:
right=middle-1
leftboder=right
else:
left=middle+1return leftboderleftboder=getLeftBoder(nums,target)
rightboder=getRightBoder(nums,target)#情况一
if leftboder==-2 or rightboder==-2: return [-1,-1]
#情况三
if rightboder-leftboder>1: return [leftboder+1,rightboder-1]
#情况二
return [-1,-1]方法2：
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
def binarySearch(nums,target):
left, right = 0, len(nums)-1
while left <= right:
middle = left+(right-left)//2
if nums[middle]>target:
right=middle-1
elif nums[middle]0 and nums[left-1]==target: left-=1
while right+1 < len(nums) and nums[right+1]==target: right+=1
return [left,right] 69.x 的平方根
题目：给你一个非负整数 x ，计算并返回 x 的算术平方根 。python 代码 方法：
由于返回类型是整数，结果只保留整数部分，小数部分将被舍去。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
class Solution:
def mySqrt(self, x: int) -> int:
left, right, ans=0,x,-1
while left <= right:
middle=left+(right-left)//2
if middle * middle <= x:
ans = middle
left = middle+1
else:
right = middle-1
return ans367.有效的完全平方数
题目：给定一个正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。【力扣算法题-python|力扣算法题总结（python）—二分查找】方法：
class Solution:
def isPerfectSquare(self, num: int) -> bool:
left, right=0,num
while left<=right:
middle = left+(right-left)//2
square = middle*middle
if square > num:
right=middle-1
elif square < num:
left=middle+1
else:
return True
return False推荐阅读
- python-opencv|5.python-opencv人脸马赛克
- Python 设计模式（单例模式）
- 人工智能|终结 Python 原生字典（这个库要逆天改命了）
- python|终结 Python 原生字典（这个库真的要逆天改命了）
- 算法|历时一年，论文终于被国际顶会接收了
- 机器学习|机器学习算法[1]--线性回归，岭回归，Lasso回归原理详解及sklearn实现
- 数据库|MySQL 暴跌！
- 为什么range不是迭代器（range到底是什么类型？）
- 大名鼎鼎的Requests库用了什么编码风格（）