搜索插入位置

WangScaler: 一个用心创作的作者。

声明：才疏学浅，如有错误，恳请指正。

题目

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

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

分析

初步思考

因为是个已经排好序的数组，在里面寻找目标值，首先想到的就是家喻户晓的二分法。每次查找中间的值，每轮减少一半的遍历。这时候的时间复杂度，恰好就是O(log n)，也满足题目要求

继续思考

要写二分法，关键的就是要找中间的数的位置。

假设我们的数组长度是5。则第三个是我们的中间位置，也就是下标为2。(0+5-1)/2=2。

假设我们的数组长度是6。则第三或第四个是我们的中间位置，也就是下标为2或3。(0+6-1)/2=3。

我们有三个指针，一个指向头指针，一个指向尾指针，另一个自然就是我们中间指针。当中间的指针的值不是我们目标值且大于我们的目标值，我们就将尾指针变为中间指针的位置 -1；当中间的指针的值不是我们目标值且小于我们的目标值，我们就将头指针变为中间指针的位置+1；直到头指针大于等于尾指针还没找到，那么目标值必然插入到当前位置的后一个位置，如果找到了，自然不必说，返回下标即可。

答案

   public static int searchInsert(int[] nums, int target) {
        int first = 0;
        int end = nums.length - 1;
        while (first <= end) {
            int mid = (end + first) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[mid] > target) {
                end = mid - 1;
            }
            if (nums[mid] < target) {
                first = mid + 1;
            }
        } 
       return first;
    }

复杂度

• 时间复杂度：O(logn)，其中 n 为数组的长度。
• 空间复杂度：O(1)。我们只需要常数空间存放三个指针的位置。

总结

这个题就是个简单的二分法，二分法是个典型的算法。

画个图，简单理解下，有序数组[1,2,3,4,5,6],目标值5。

• 第一轮，头节点在0的位置，尾节点在5的位置，中间节点在2的位置。对比3小于目标值5。

• 第二轮，移动头节点到中间节点+1的位置3。移动中间节点到(3+6-1)/2=4。对比就是目标值返回下标4。

都来了，点个赞再走呗！

关注WangScaler，祝你升职、加薪、不提桶！