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

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

class Solution {
public:
    int searchInsert(vector& 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;
    }
};