每日一题（LeetCode · 35）搜索插入位置

题目：

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

请必须使用时间复杂度为 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

解题思路：参考java，Arrays提供的二分查找法里面的原码解题，

java提供的源码：

private static int binarySearch0(int[] a, int fromIndex, int toIndex,
                                     int key) {
        int low = fromIndex;
        int high = toIndex - 1;

        while (low <= high) {
            int mid = (low + high) >>> 1;
            int midVal = a[mid];

            if (midVal < key)
                low = mid + 1;
            else if (midVal > key)
                high = mid - 1;
            else
                return mid; // key found
        }
        return -(low + 1);  // key not found.
    }

官方解释：最后找不到返回 负的插入点减一；

让我们看看解题步骤：

解题步骤：

1. 初始化两个指针，一个指向数组的开始（low），一个指向数组的结束（high）。
2. 计算中间元素的索引 mid = (low + high) >>> 2（使用整数除法）。
3. 检查中间元素是否是要查找的元素。如果是，返回 mid。
4. 如果要查找的元素小于中间元素，更新 high = mid - 1，  并在数组的左半部分重复步骤 2 和 3。
5. 如果要查找的元素大于中间元素，更新 low = mid + 1，并在数组的右半部分重复步骤 2 和 3。
6. 如果 low > high，说明元素不在数组中，返回 -1 或其他表示未找到的值。

再看看图解过程：

（1）找不到的情况：

（2）找到的情况；

代码如下：

class Solution {
    public int searchInsert(int[] nums, int target) {
        //定义一个指针指向第一个元素
        int i = 0;
        //定义另一个指针指向另一个元素
        int j = nums.length - 1;
        while (i <= j) {
            //定义指针，指向中间元素
            int mid = (i + j) / 2;
            if (target > nums[mid]) {
                i = mid + 1;
            }else if (target < nums[mid]) {
                j = mid - 1;
            }else {
                //找到的情况，返回索引
                return mid;
            }
        }
        //没有找到，返回i指针
        return i;
    }
}

好了，时间不负有心人，小伙伴们，今天就到这里。有帮助的话留下关注再走吧！别偷偷收藏不关注哦！