力扣刷题--数组--第一天

一、数组

数组特点：

连续内存空间
存储得数据元素类型一致
数组可以通过下标索引查找数据元素，可以删除、替换、添加元素等

1.1 二分查找

使用二分查找需满足得条件：

数组是有序的；
数组中没有重复元素；
查找的target是唯一的。
注意写代码时数组左右区间。

题目链接
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
python：

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) 的算法
暴力解法

python">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；
在这里插入图片描述

图像参考自https://leetcode.cn/circle/discuss/ooxfo8/

代码：

python"># [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，我困惑许久，不太懂为何会是这样的结果。究其根本还是对二分查找算法不够理解，经过多方查找资料才对上述结果有了一定的理解。

图像参考自https://leetcode.cn/circle/discuss/ooxfo8/

有如下结论：对于左闭右闭区间情况，

初始状态：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/