网站备案 备注关联性,视频模板网,视频素材库网站下载,全球知名电子商务网站统计1.二分查找 给定一个 n 个元素有序的#xff08;升序#xff09;整型数组 nums 和一个目标值 target #xff0c;写一个函数搜索 nums 中的 target#xff0c;如果目标值存在返回下标#xff0c;否则返回 -1。示例 1: 输入: nums [-1,0,3,5,9,12], target 9
输出: 4
解… 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):# 定义左右边界left0rightlen(li) - 1while (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 midreturn -1 2.在排序数组中查找元素的第一个和最后一个位置 给你一个按照非递减顺序排列的整数数组 nums和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target返回 [-1, -1]。 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。 首先这个题目分为三种情况1.待查找目标值在数组中例如[1,2,3,5,5,6,7] target5
此时返回值为[3,4] 2.待查找目标值不在数组中但其大小范围在li中[1,2,3,5,5,6,7] target4
3,待查找目标值不在数组中且不在li范围内[1,2,3,5,5,6,7] target8 。23两种情况此时都返回[-1,-1]
def search(li,target):def search_LeftBorder(li,target):left 0right len(li)-1leftBorder-2while (leftright):mid left(right-left)//2if (li[mid]target):right-1leftBorderright # 当li[mid]target的时候更新rightelse:left-1return leftBorderdef search_RightBorder(li,target):left 0right len(li)-1rightBorder-2while (leftright):mid left(right-left)//2if (li[mid]target):right-1else:left-1 # 当li[mid]target的时候更新leftrightBorderleft return rightBorderleftBorder search_LeftBorder(li,target)rightBorder search_LeftBorder(li,target)if leftBorder-2 or rightBorder-2:return [-1,-1]elif (rightBorder-leftBorder)1:return [leftBorder1,rightBorder-1]return [-1,-1]3.X的平方根 给你一个非负整数 x 计算并返回 x 的 算术平方根 。 由于返回类型是整数结果只保留 整数部分 小数部分将被 舍去 。 注意不允许使用任何内置指数函数和算符例如 pow(x, 0.5) 或者 x ** 0.5 。 def mySqrt(x)if x1: return xleft,right0,xwhile rightleft:mid left(right-left)//2if mid *mid x:leftmid1else:right mid-1return right 4. 有效的完全平方数 给你一个正整数 num 。如果 num 是一个完全平方数则返回 true 否则返回 false 。 完全平方数 是一个可以写成某个整数的平方的整数。换句话说它可以写成某个整数和自身的乘积。 不能使用任何内置的库函数如 sqrt 。 def isPerfectSquare(num):rightnumleft0sFalsewhile (rightleft):mid left(right-left)//2if mid * mid num:right mid -1elif mid * mid num:left mid1elif mid *mid num:sTruebreakreturn s
