力扣题解之：搜索插入位置

2021-08-12 02:47:13  晓掌柜  版权声明：本文为站长原创文章，转载请写明出处

一、题目

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

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

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

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

    提示:

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

二、解题思路

        因为是在有序数组中寻找元素，所以无外乎有下面四种情况：

        ① 目标值在数组所有元素之前
        ② 目标值等于数组中的某一个元素
        ③ 目标值不存在数组元素中，等于插入后的位置
        ④ 目标值在所有元素之后

        使用二分法可以很好的解决这个问题...

三、解题答案

class Solution {
    public int searchInsert(int[] nums, int target) {
        /* 因为是排序数组，首先检测是否在目标数据范围内'
           如果不在则需要新增到数组中--返回数组长度的下标
           如果在就使用二分法去处理就好了
        * */
        int beginIndex = 0;
        int endIndex = nums.length - 1;
        while(beginIndex <= endIndex){
            /* 获取中间值 */
            int middleIndex = (endIndex + beginIndex) / 2;
            System.out.println("获取到中间值为：" + middleIndex);
            if(nums[middleIndex] > target){
                /* 在前半段 */
                endIndex = middleIndex - 1;
                System.out.println("在前半段");
            }else if (nums[middleIndex] < target){
                /* 在后半段 */
                beginIndex = middleIndex + 1;
                System.out.println("在后半段，下一次起始下标为：" + beginIndex + " -- " + endIndex);
            }else{
                /* 命中下标 */
                return middleIndex;
            }
        }
        return beginIndex;
    }
}

四、执行结果