leetcode 35搜索插入位置

ゞ浴缸里的玫瑰 2023-06-15 11:20 7阅读 0赞

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

你可以假设数组中无重复元素。

示例 1:

输入: \[1,3,5,6\], 5  
输出: 2  
示例 2:

输入: \[1,3,5,6\], 2  
输出: 1  
示例 3:

输入: \[1,3,5,6\], 7  
输出: 4  
示例 4:

输入: \[1,3,5,6\], 0  
输出: 0

特殊的二分查找法：

class Solution {
        
        public int searchInsert(int[] nums, int target) {
        
            int l = 0;
            int r = nums.length;
    
            while (l < r) {
        
                int mid = l+(r-l)/2;
                if (nums[mid] == target) {
        
                    return mid;
                } else if (nums[mid] > target) {
        
                    r = mid;
                } else if (nums[mid] < target ) {
        
                    l = mid + 1;
                }
             }
             return l;
        }
    }

讲讲二分插入，二分查找其实没那么好写，通过一些细节就能达到不同的效果。  
int len = nums.length;  
if (nums\[len - 1\] < target) \{  
return len;  
\}

int left = 0;
        int right = len - 1;
    
        while (left <= right) {
            int mid = (left + right) / 2;
            // 等于的情况最简单，我们应该放在第 1 个分支进行判断
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                // 题目要我们返回大于或者等于目标值的第 1 个数的索引
                // 此时 mid 一定不是所求的左边界，
                // 此时左边界更新为 mid + 1
                left = mid + 1;
            } else {
                // 既然不会等于，此时 nums[mid] > target
                // mid 也一定不是所求的右边界
                // 此时右边界更新为 mid - 1
                right = mid - 1;
            }
        }
        // 注意：一定得返回左边界 left，
        // 如果返回右边界 right 提交代码不会通过
        // 【注意】下面我尝试说明一下理由，如果你不太理解下面我说的，那是我表达的问题
        // 但我建议你不要纠结这个问题，因为我将要介绍的二分查找法模板，可以避免对返回 left 和 right 的讨论
    
        // 理由是对于 [1,3,5,6]，target = 2，返回大于等于 target 的第 1 个数的索引，此时应该返回 1
        // 在上面的 while (left <= right) 退出循环以后，right < left，right = 0 ，left = 1
        // 根据题意应该返回 left，
        // 如果题目要求你返回小于等于 target 的所有数里最大的那个索引值，应该返回 right
    
        return left;

引自leetcode上一个解答。

细节就在 while判断，以及分支的mid+1，-1等等的情况。