一、数组
数组特点：
- 连续内存空间
- 存储得数据元素类型一致
- 数组可以通过下标索引查找数据元素，可以删除、替换、添加元素等
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 -1
mid=lindex+(rindex-lindex)//2
if nums[mid] == target:
return mid
elif nums[mid] > target:
rindex=mid-1
else:
lindex=mid+1
return 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;
else
return 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=0
rindex=len(nums)-1
while lindex <= rindex:
mid=lindex+(rindex-lindex)//2
if nums[mid] > target:
rindex=mid-1
elif nums[mid] < target:
lindex=mid+1
else:
return mid
return 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；