35. 搜索插入位置

题目

• 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

---

理解：最基础的二分搜索

• while(left < right)

• int mid = (right +left) >> 1 —————————- 向下取整

• if(target < num[mid]) left = mid + 1;—————-这样不会陷入死循环

• else right = mid;

例题

输入: [1,3,5,6], 5

输出: 2

输入: [1,3,5,6], 2

输出: 1

解题

• 二分法

---

代码

int searchInsert(vector<int>& nums, int target) {
        int len = nums.size();
        if(len==0)return 0;
        if(target > nums[len - 1])return len;

        int left = 0;
        int right = len - 1;
        while(left < right){
            //int mid = (left + right) >>1;   //向下取整 
            int mid = left + (right-left)/2; 
            if(nums[mid] == target){
                return mid ;
            }

            if(nums[mid] < target){
                left = mid + 1;
            }
            else{
                right = mid;
            }
        }
        return left;
    }