1.二分查找
给定一个
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
def binary_search(li,target):
# 定义左右边界
left=0
right=len(li) - 1
while (left <= right):
mid = left + (right - left) // 2 # 防止溢出
if li[mid] > target:
right = mid - 1 # 这里等于减1是因为上面我们用的小于等于此时该mid数已经判断过
elif li[mid] < target:
left = mid + 1 # 同理
else:
return mid
return -1
2.在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组
nums，和一个目标值target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值target，返回[-1, -1]。你必须设计并实现时间复杂度为
O(log n)的算法解决此问题。
首先这个题目分为三种情况，1.待查找目标值在数组中例如：[1,2,3,5,5,6,7] target=5
此时返回值为：[3,4] 2.待查找目标值不在数组中但其大小范围在li中，[1,2,3,5,5,6,7] target=4
3,待查找目标值不在数组中且不在li范围内，[1,2,3,5,5,6,7] target=8 。2，3两种情况此时都返回[-1,-1]
def search(li,target):
def search_LeftBorder(li,target):
left = 0
right = len(li)-1
leftBorder=-2
while (left<=right):
mid = left+(right-left)//2
if (li[mid]>=target):
right-=1
leftBorder=right # 当li[mid]=target的时候更新right
else:
left-=1
return leftBorder
def search_RightBorder(li,target):
left = 0
right = len(li)-1
rightBorder=-2
while (left<=right):
mid = left+(right-left)//2
if (li[mid]>target):
right-=1
else:
left-=1 # 当li[mid]=target的时候更新left
rightBorder=left
return rightBorder
leftBorder = search_LeftBorder(li,target)
rightBorder = search_LeftBorder(li,target)
if leftBorder==-2 or rightBorder==-2:
return [-1,-1]
elif (rightBorder-leftBorder)>1:
return [leftBorder+1,rightBorder-1]
return [-1,-1]
3.X的平方根
给你一个非负整数
x，计算并返回x的 算术平方根 。由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如
pow(x, 0.5)或者x ** 0.5。
def mySqrt(x)：
if x<=1: return x
left,right=0,x
while right>=left:
mid =left+(right-left)//2
if mid *mid <=x:
left=mid+1
else:
right = mid-1
return right
4. 有效的完全平方数
给你一个正整数
num。如果num是一个完全平方数，则返回true，否则返回false。完全平方数 是一个可以写成某个整数的平方的整数。换句话说，它可以写成某个整数和自身的乘积。
不能使用任何内置的库函数，如
sqrt。
def isPerfectSquare(num):
right=num
left=0
s=False
while (right>=left):
mid = left+(right-left)//2
if mid * mid > num:
right = mid -1
elif mid * mid < num:
left = mid+1
elif mid *mid ==num:
s=True
break
return s
