二分查找：
二分法写法：
二分法的写法共分两种分别是：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]<target:
left=middle+1
else:
return middle
return right+1
方法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]<target:
left=middle+1
else:
return middle
return right
34.在排序数组中查找元素的第一个和最后一个位置
题目：给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
解析
寻找target在数组里的左右边界，有如下三种情况：
情况一：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=left
return rightboder
def 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+1
return leftboder
leftboder=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]<target:
left=middle+1
else:
return middle
return -1
index=binarySearch(nums,target)
#情况一，情况二
if index==-1: return [-1,-1]
#情况三
left, right = index, index
while left-1 >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 的算术平方根 。
由于返回类型是整数，结果只保留整数部分，小数部分将被舍去。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
python 代码
方法：
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 ans
367.有效的完全平方数
题目：给定一个正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
方法：
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