二分法 | 35. 搜索插入位置

一、题目

二、题解

二分法的时候，退出循环的条件为left > right，但是总是存在着left == middle 或 right == middle 的情况。当left == middle时，说明right < middle，即 nums[middle] > target，反之同理。此时即可得到要插入的位置下标为righ的值，反之同理。

三、代码

class Solution {
    
public:
    int searchInsert(vector<int>& nums, int target) {
    
        int left = 0;
        int right = nums.size() - 1;
        int middle;
        while(left <= right){
    
            middle = left + right;
            if(nums[middle] == target ){
    
                return middle;
            }else if(nums[middle] > target){
    
                right = middle - 1;
            }else{
    
                left = middle + 1;
            }
        }
        if(right < 0){
    
            right = 0;
        }
        return left > middle ? left : right;
    }
};