35.搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

1
2
输入: nums = [1,3,5,6], target = 5
输出: 2

寻找数组中的某个位置

Solution:

既然题目要求了时间复杂度，那么只有用二分查找解决

如果nums数组内有target，那么二分查找可以找到并返回，如果没有target，那么最后的mid的值正好是其插入位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public int searchInsert(int[] nums, int target) {
       // 初始化搜索的范围为整个数组
       int low = 0; // 搜索范围的下界
       int high = nums.length - 1; // 搜索范围的上界

       // 当上界不小于下界时，继续搜索
       while (high >= low) {
           // 计算当前搜索范围的中点
           int mid = (low + high) / 2;
           
           // 如果中点的值大于目标值，则调整上界到中点左侧，继续在左半边搜索
           if (nums[mid] > target) {
               high = mid - 1;
           } 
           // 如果中点的值小于目标值，则调整下界到中点右侧，继续在右半边搜索
           else if (nums[mid] < target) {
               low = mid + 1;
           } 
           // 如果中点的值等于目标值，直接返回中点索引
           else {
               return mid;
           }
       }
       
       // 如果循环结束还没找到目标值，说明目标值不在数组中，
       // 此时low指向的就是按顺序插入目标值应该位于的位置
       return low;
    }
}