上次刷没刷完整，和李哥做字节的题感觉先前刷的题白刷了，故打算从头到尾完整走一遍。
二分法
1-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
解释: 2 不存在 nums 中因此返回 -1
提示：
- 你可以假设 nums 中的所有元素是不重复的。
- n 将在 [1, 10000]之间。
- nums 的每个元素都将在 [-9999, 9999]之间
class Solution:
def search(self, nums: List[int], target: int) -> int:
l,r = 0,len(nums)-1
while l < r:
mid = l + r + 1 >> 1
if nums[mid] > target:
r = mid - 1
else:
l = mid
if nums[l] == target:
return l
return -1
RE了一次，原因是r的右侧初始化写成了len(nums)
1-2.搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n)的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2
示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1
示例 3:
输入: nums = [1,3,5,6], target = 7
输出: 4
提示:
- 1
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
l,r = 0,len(nums)-1
while l> 1
if nums[mid] < target:
l = mid
else:
r = mid - 1
if nums[l] < target:
return l + 1
return l
一直WA，两个板子
第一个板子就是找第一个小于target值的位置，所以位置不能取到外面
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
l,r = 0,len(nums)
while l> 1
if nums[mid] >= target:
r = mid
else:
l = mid + 1
return l
这里和上面不一样，这里可以取到数组外面，我们找到的是第一个大于等于target的位置，所以可能取到len(nums)
总结：务必考虑清楚找到的是什么，然后敲定范围
1-3.在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
示例 2：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
示例 3：
输入：nums = [], target = 0
输出：[-1,-1]
提示：
- 0
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
left,right = -1,-1
if len(nums) == 0:
return [-1,-1]
l,r = 0,len(nums) - 1
while l < r:
mid = l + r >> 1
if nums[mid] >= target:
r = mid
else:
l = mid + 1
if nums[l] == target:
left = l
l,r = 0,len(nums) - 1
while l < r:
mid = l + r + 1 >> 1
if nums[mid]
一次AC了，但存在两个编写时的问题
一是一开始left和right搞反了，上面是>=，所以是第一个大于等于target的位置，所以是左侧。相反下面的为右侧。
二是 nums = [], target = 0 RE了，特判一下
1-4.x 的平方根
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1：
输入：x = 4
输出：2
示例 2：
输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
提示：
- 0
class Solution:
def mySqrt(self, x: int) -> int:
if x == 0: return 0
if x > 1
if mid * mid > x:
r = mid - 1
else:
l = mid
return l
一次AC了，可能就是要考虑是大于x时才是不可能的完全不可能的情况，平方根乘起来必然
Original: https://www.cnblogs.com/ydssx7/p/16642223.html
Author: ydssx
Title: 代码随想录-数组篇
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/587535/
转载文章受原作者版权保护。转载请注明原作者出处！