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
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
