整数二分查找 leetcode35. 搜索插入位置 leetcode704. 二分查找

这两道题的本质是一样的，都是整数二分查找。题目给出的条件比较强，序列是严格单调递增的。

但是我这个即使序列存在重复的元素也可以满足需求

35. 搜索插入位置

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int size = nums.size();
        int i = 0,j = size - 1;
        int mid = (i+j)/2;
        while(i <= j){
            if(target > nums[mid])    i = mid + 1;           
            else    j = mid - 1;           
            mid = (i+j)/2;
        }
        return i;
    }
};
//i <= j
//if(target > nums[mid])    i = mid + 1; 
//return i
//记住这三个最重要的点，可以免得次次使用二分都得调试

704. 二分查找

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int size = nums.size();
        int i = 0,j = size - 1;
        int mid = (i+j)/2;
        while(i <= j){
            if(target > nums[mid])  i = mid + 1;         
            else    j = mid - 1;         
            mid = (i+j)/2;
        }
        if(i == size || nums[i] != target)  return -1;  //i 不会在左边越界。
        //如果 i 在右边越界了，或者结束时不是要找的target，那么target就不存在
        return i;
    }
};