一、数组
数组特点:
- 连续内存空间
- 存储得数据元素类型一致
- 数组可以通过下标索引查找数据元素,可以删除、替换、添加元素等
1.1 二分查找
使用二分查找需满足得条件:
- 数组是有序的;
- 数组中没有重复元素;
- 查找的target是唯一的。
- 注意写代码时数组左右区间。
- 题目链接
给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。
python:
# [left,right]查找区间是左闭右闭
class Solution:def search(self, nums: List[int], target: int) -> int:def run(lindex,rindex):if lindex > rindex:return -1mid=lindex+(rindex-lindex)//2if nums[mid] == target:return midelif nums[mid] > target:rindex=mid-1else:lindex=mid+1return run(lindex,rindex)return run(0,len(nums)-1)
c++版代码:
class Solution {
public:int search(vector<int>& nums, int target) {int lindex=0;int rindex=nums.size()-1;while(lindex <= rindex){int mid=lindex+(rindex-lindex)/2;if(nums[mid] > target)rindex=mid-1;else if(nums[mid] < target)lindex=mid+1;elsereturn mid;}return -1;}
};
- 题目链接
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法
暴力解法
class Solution:def searchInsert(self, nums: List[int], target: int) -> int:for i in range(len(nums)):# 因为nums是升序数组,故出现的第一个大于或等于target的索引满足条件if nums[i]>=target:return i# 若上述均不满足,说明target大于nums数组全部元素# 故将target插到数组尾部return len(nums)
二分查找
首先下述讨论均以左闭右闭区间为例。设定lindex、rindex、mid分别为左边索引、右边索引、中间索引,根据二分查找规则,若数组中没有target,则有lindex>rindex,且lindex=rindex+1。
根据题意,可分为四种情况:
(1) 若target小于数组全部元素,故lindex不更新,lindex=0,rindex最终为-1,target插入的索引为0;
(2) 若target大于数组全部元素,则rindex不更新,rindex=n-1,lindex最终更新的n,target插入的索引为n;
(3) 若target等于数组中某个元素,则根据二分查找规则,直接返回mid索引即可;
(4) 若target需插入数组中某个位置,根据上述暴力求解法可以看出,target肯定会插在第一个大于target的索引位置上。根据左闭右闭区间规则,最终target因为不在数组中,则有lindex>rindex跳出循环,此时看下图可知,lidnex左侧的元素必定小于target,则lindex是第一个大于target的索引;从rindex角度来看,rindex右侧的元素必定大于target,故lindex是第一个大于target的索引。故target插入的索引为lindex或者是rindex+1;
代码:
# [left,right]
class Solution:def searchInsert(self, nums: List[int], target: int) -> int:# [lindex,rindex]lindex=0rindex=len(nums)-1while lindex <= rindex:mid=lindex+(rindex-lindex)//2if nums[mid] > target:rindex=mid-1elif nums[mid] < target:lindex=mid+1else:return midreturn lindex # rindex+1
总结
- 目前只关注二分查找左闭右闭区间情况,怕与其他情况弄混。之后熟悉了可以再看其他解法;
- 第2题对于最终返回的是lindex或者rindex+1,我困惑许久,不太懂为何会是这样的结果。究其根本还是对二分查找算法不够理解,经过多方查找资料才对上述结果有了一定的理解。
有如下结论:对于左闭右闭区间情况,
- 初始状态:lindex=0,rindex=n-1;
- 循环条件:lindex<=rindex;
- 中间值索引:mid=lindex+(rindex-lindex)//2;
- nums[mid] > target, update>> rindex=mid-1;
- nums[mid] < target, update>> lindex=mid+1;
- 满足条件:return mid;
- 跳出循环:lindex>rindex 且 lindex=rindex+1;
参考:
- https://www.programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html#%E6%80%9D%E8%B7%AF
- https://programmercarl.com/0035.%E6%90%9C%E7%B4%A2%E6%8F%92%E5%85%A5%E4%BD%8D%E7%BD%AE.html#%E6%80%9D%E8%B7%AF
- https://leetcode.cn/circle/discuss/ooxfo8/