leet code 35.搜索插入位置

简单题蕴含大学问

link leet code 35.搜索插入位置

思路历程

学习算法已有时日，再做这一道简单程度的二分题目时-发现还是不能游刃有余地掌握。 题目中要求：需要在数组中找到目标值，并返回其索引，如果目标值不存在于数组中的话，返回其将会被顺序插入的位置。 那么有两种情况

1. 目标值在数组中存在
2. 目标值在数组中不存在

如何兼顾这两种情况呢？

• 首先考虑目标值在数组中存在的情况。

int mid = (low + high) / 2;
if (arr[mid] == target) {
    // 找到目标值，退出循环
} else if (arr[mid] < target) {
    low = mid + 1; // 更新low
} else {
    high = mid - 1; // 更新high
}

• 明确目标：也就是说，需要找到目标值所在的索引位置。如果不在的话，返回下一位。
• 代码如何实现？

class Solution {
    public int searchInsert(int[] nums, int target) {
        int len = nums.length;
        // 初始化结果
        int ans = len;
        int left = 0,right = len - 1;

        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] >= target) {
                // 这里用 ans 记录查找的目标元素的位置。
                // 一定不会遗漏
                // 当数组元素存在的时候，ans 输出目标值所在位置的索引
                // 当数组元素不存在的时候，ans 数组最接近目标值所在位置的索引
                // 初始化 ans = len，即当目标值大于数组中元素的最大值的时候，需要插入的位置是  len.
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return ans;
    }
}

二分算法小技巧

确定边界条件

在使用二分算法时，边界条件非常重要，需要仔细考虑。可以通过画图或者手动模拟的方式，验证边界条件是否正确。

确定中间值

在计算中间值时，需要注意整数除法的向下取整规则。如果使用C++或Java等语言，可以使用整数除法符号“/”或位运算符号“>>”来计算中间值。

注意特殊情况

在使用二分算法时，需要注意特殊情况，比如查找第一个大于目标值的位置、查找最后一个小于目标值的位置、查找旋转排序数组中的最小值等。这些特殊情况可能需要对二分算法进行一些变形或扩展。