一. 简介
本文记录力扣网上题目，涉及数组的逻辑题：在数组中搜索某个值，返回其index，如果没有则返回可以插入的index。
二. 力扣网C语言编程题：搜索插入位置
题目：搜索插入问题
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
要求：请必须使用时间复杂度为 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 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 为 无重复元素 的 升序 排列数组
-104 <= target <= 104
题目分析：
这道题目要求时间复杂度为logn，可以使用二分法实现。
题目说排序数组，一般默认情况下是升序数组，即数组中元素大小是从小到大排序的。
什么是二分法？
二分法又名二分查找法或折半查找法。二分法查找法是一种在有序数组或有序列表中查找特定元素的高效方法。
二分查找法因为每次迭代查找都会将区间折半，具体如下：
- 初始搜索区间长度为
n； - 第一次迭代后，区间长度变为
n/2； - 第二次迭代后，区间长度变为
n/4； - 以此类推，直到区间长度为
1（最多迭代log₂n次）。
因此，迭代次数的上界为 log₂n，每次迭代的操作（如计算中点、比较值）均为 O(1)，故总时间复杂度为 O(log n)。
解题思路：
1. 首先，定义左边界: left = 0，右边界: right = n-1（其中n为数组的索引）；
2. 遍历数组，循环判断条件是 left <= right，这里 包含 left ==right的判断是考虑 target不在数组范围内的情况（可以通过例子来简单验证）；
3. 循环内部：
（1）计算数组中间元素d的索引： mid = (left+right)/2；
（2）判断 target 与 nums[mid]这个中间值的大小：
如果 target == nums[mid]；则返回 mid；
如果 target < nums[mid]，则 说明 target在数组的左边，更改右边界：right = mid-1；
如果 target > nums[mid]，则 说明 target在数组的右边，更改右边界：right = mid+1；
C语言实现如下：
//二分法
int searchInsert(int* nums, int numsSize, int target) {
if((nums == NULL) || (numsSize <= 0)) {
return -1;
}
int left = 0;
int right = numsSize-1;
int mid = 0;
//这里 left<=right判断，考虑target不是数组范围内的情况
while(left <= right){
mid = (left+right)/2;
if(target == nums[mid]) {
return mid;
}
//target < nums[mid]中间值，则说明target在数组左边
//更改右边界：right= mid-1;
else if(target < nums[mid]) {
right = mid-1;
}
else {//target < nums[mid]中间值，则说明target在数组右边
//更改右边界：left= mid+1;
left = mid+1;
}
}
return left;
}可以看出，时间复杂度为 logn，空间复杂度为 O(1)；
二分法使用 python实现如下：
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
n = len(nums)
left = 0 #左边界为数组首元素的索引
right = (n-1) #右边界为数组最后一个元素的索引
#这里left<=right判断，考虑target不是数组范围内的情况
while(left <= right):
mid = (left+right)//2 #python除法，向下取整
if(target == nums[mid]):
return mid
elif(target < nums[mid]):
#target < 区间中间元素值，则说明target在数组左边
right = mid-1
else: #target > 区间中间的元素值，则说明target在数组的右边
left = mid+1
return left