算法求生 每日刷题记录（三）

1.题目描述

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

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/search-insert-position
1
2
3
4
5
6

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

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

示例3：
输入: nums = [1,3,5,6], target = 7
输出: 4
1
2
3

提示

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums 为 无重复元素 的 升序 排列数组
• -104 <= target <= 104

2.解题思路

​ 首先可以了解一下二分查找的思路

二分查找针对的是一个有序的数据集合,查找思想有点类似于分治思想。每次都通过跟区间的中间元素对比,将查找的区间缩小为之前的一半,直到找到要查找的元素

栗子1：nums = [1,3,5,6], target = 5
第一次 取出中间元素 3 --->  3 < 5 所以 3之前的元素就没必要查找了  --->    [5,6]
第二次 取出中间元素 5 --->  5 = 5 找到了

栗子2：nums = [1,3,5,6], target = 2
第一次 取出中间元素 5 --->  5 > 2 所以 5之后的元素就没必要查找了  --->    [1,3]
第二次 取出中间元素 1 --->  1 < 2 所以 1之前的元素就没必要查找了  ---> [3]
第三次 取出中间元素 3 ---> 3 > 2 没找到 因为 3 > 2 所以位置是 3的位置 - 1

栗子3：nums = [1,3,5,6], target = 7
第一次 取出中间元素 3 --->  3 < 7 所以 3之前的元素就没必要查找了  --->    [5,6]
第二次 取出中间元素 5 --->  5 < 7 所以 5之前的元素就没必要查找了  ---> [6]
第三次 取出中间元素 6 ---> 6 < 7 没找到 因为 7 > 6 所以位置是 6的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14

3.代码实现

public int searchInsert(int[] nums, int target) {
        int left = 0,right = nums.length-1;
        int c = 0;
        while (left <= right){
           c = (left+right)/2;
            if(target > nums[c]){
                left = c+1;
            }else if (target < nums[c]) {
                right = c-1;
            }else {
                return  c;
            }
        }
        if(nums[c] > target){ //c的位置就是最终target要放入的位置 有序
            return c;
        }else{
            return  c+1;
        }

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

4.运行结果