日野弥生：勉強しよう

binary search

发表于2024年12月12日

介绍

二分查找（英语：binary search），也称折半搜索（英语：half-interval search）、对数搜索（英语：logarithmic search），是用来在一个有序数组中查找某一元素的算法。

过程

以在一个升序数组中查找一个数为例。

它每次考察数组当前部分的中间元素，如果中间元素刚好是要找的，就结束搜索过程；如果中间元素小于所查找的值，那么左侧的只会更小，不会有所查找的元素，只需到右侧查找；如果中间元素大于所查找的值同理，只需到左侧查找。

实现

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int end = nums.size()-1,start=0;

        while(start <=end)
        {
        int mid = start + ((end - start) >> 1);
        if(target<nums[mid])
            end =mid-1;
        else if(target>nums[mid])
            start = mid+1;
        else 
            return mid;
        }
        return start;
    }
};

边界条件

A、 while(start <=end);

start <= end：这个条件确保了当 start 和 end 相等时，也能够继续执行循环体，进行最后的比较。即使 start 和 end 指向同一个位置，循环依然会进行一次中间值的计算，并判断 nums[mid] 是否等于目标值 target。

start < end：如果使用这个条件，最后当 start == end 时，循环会停止。此时，mid 已经没有机会与 target 比较。因此，可能会错过需要处理的最后一个元素。

B、 start = mid+1; end =mid-1;

迭代条件维持时，循环变体需要避免掉重复的部分。

C、 return start;

当目标值 target 不在数组中时，start 会指向目标值应该插入的位置。

分类讨论： 1、最后的区间为$[n,n+1]$时，start和mid指向n,end指向n+1； 如果target==n时，结果为n，即start或者end; 如果target < n时，结果为n，即start或者end; 如果target > n时，（此时应该移位），结果为n+1, 即start或者end+1；

2、最后的区间为$[n]$时，start、mid和end都指向n； 如果target==n时，结果为n，即start或者end; 如果target < n时，结果为n，即start或者end; 如果target > n时，（此时应该移位），结果为n+1, 即start或者end+1；

综上，return start。