通过模拟保证随时随地正确写出二分搜索法

本文主要是介绍通过模拟保证随时随地正确写出二分搜索法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

二分搜索法

这算得上是简单的一种算法了, 对有序序列进行二分查找，重点是注意边界值。
写关于边界值的问题最好通过模拟, 比如: [1, 2], 两个元素, left = 0, right = 1, mid = (right + left) / 2 = 0
nums[mid] = 1 => search 3 => left = mid + 1 = 1 => left == right, nums[left] = 2 < 3, left = mid + 1, left位置也就是插入位置
做一个简单的模拟可以保证边界问题顺利解决。

代码

二分查找法

class Solution {
    public int search(int[] nums, int target) {
        // 做预处理
        if (target < nums[0] || target > nums[nums.length - 1]) {
            return -1;
        }
        // 二分法:[left,right]
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (target < nums[mid]) {
                right = mid - 1;
            } else if (target > nums[mid]) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }
}

二分查找并插入

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (target < nums[mid]) {
                right = mid - 1;
            } else if (target > nums[mid]) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return left; //没有搜索到, 返回插入位置: 这个时候最好模拟, 比如 [3, 5], 查找 4, left == right, nums[left] = 5, right--, 退出, 插入left位置
        
    }
}

这篇关于通过模拟保证随时随地正确写出二分搜索法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！