leetcode 35 搜索插入位置 Search Insert Position 二分查找 c++实现_leetcode 35 c++

二分查找很简单：两种 一种递归 一种循环

这道题分两种情况：1.查的数在排序数组里，输出查到的点的位置信息就行

                                   2.查的数不在数组里，输出它应该在的地方，这里就几个小难点，没处理好有用例就过不了 （一个情况start=end,一个情况end<start，但是都能用mid=start+end/2来与所求点比较）

代码如下：

​class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int start=0;
        int end=nums.size()-1;
        if(target<nums[0]){//比最小的还小 放在0位置
            return 0;
        } 
        if(target>nums[end]){//比最大的还大，放在最大➕1
            end=end+1;
            return end;
        }
        while(start<end){//这个while就是循环二分查找 
            int mid=(start+end)/2;
            if(target==nums[mid]){
                return mid;
            }
            else if(target<nums[mid]){
                end=mid-1;
            }
            else if(target>nums[mid]){
                start=mid+1;
            }
        }
        int mid=(start+end)/2;//存一下找到最后的开头和结尾 
            if(target>nums[mid]){//如果这个点要比你最后查的中结点还大 当然向后移一个位置 如果这个点比你现在mid小 那就放在这个mid位置 当前的mid点向后移 
                  mid=mid+1; 
            }
        return mid;
    }
};