算法积累-01

╰半橙微兮° 2023-09-30 11:02 4阅读 0赞

一、二分查找

说个段子：有一天小明到图书馆借了 N 本书，出图书馆的时候，警报响了，于是保安把小明拦下，要检查一下哪本书没有登记出借。小明正准备把每一本书在报警器下过一下，以找出引发警报的书，但是保安露出不屑的眼神：你连二分查找都不会吗？于是保安把书分成两堆，让第一堆过一下报警器，报警器响；于是再把这堆书分成两堆…… 最终，检测了 logN 次之后，保安成功的找到了那本引起警报的书，露出了得意和嘲讽的笑容。于是小明背着剩下的书走了。 从此，图书馆丢了 N - 1 本书。

题目：给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1

class Solution {
        public int search(int[] nums, int target) {
            // 定义target在左闭右闭的区间里，[left, right]
            int left = 0;
            int right =nums.length - 1;
            //二分法循环查找
            while(left<=right){//当left==right，区间[left, right]依然有效，所以用 <=
                int middle = left + ((right-left)/2);// 防止溢出 等同于(left + right)/2
                // target 在左区间，所以[left, middle - 1]
                if(nums[middle]>target){
                    right = middle-1;
                }
                // target 在右区间，所以[middle + 1, right]
                else if(nums[middle]<target){
                    left = middle+1;
                }
                // nums[middle] == target
                else{
                    return middle;
                }
            }
            // 未找到目标值
            return -1;
        }
    }

二分查找涉及的很多的边界条件，逻辑比较简单，但就是写不好。例如到底是 `while(left < right)` 还是 `while(left <= right)`，到底是`right = middle`呢，还是要`right = middle - 1`呢？

大家写二分法经常写乱，主要是因为对区间的定义没有想清楚，区间的定义就是不变量。要在二分查找的过程中，保持不变量，就是在while寻找中每一次边界的处理都要坚持根据区间的定义来操作，这就是\*\*循环不变量\*\*规则。

写二分法，区间的定义一般为两种，左闭右闭即\[left, right\]，或者左闭右开即\[left, right)。

middle不能用（left+right）/2形式，当left和right都是int，两个值的初始值都超过int限定大小的一半，那么left+right就会发生溢出，所以应该用left+(right-left)/2来防止求中值时候的溢出