[35. Search Insert Position]

(https://leetcode.cn/problems/search-insert-position/)

• 此题是从一个升序数组且数组内元素不重复查找目标值，因此首选二分法
• 二分法前提：
  • 有序数组
  • 数组内元素不重复
• 此题难点是如何确定最终结果的index
  • 若 nums[middle] == target ，直接return middle
  • 但对于大于和小于这两种情况，则需找找规律：
    • 最终没有找到target会退出循环，若target依然大于middle（也就是left和right下标对应值），则left = middle + 1，那么很显然，return left；但若target小于middle，则right = middle - 1，很显然依旧return left
  • 综上所述，在最终没有找到target退出循环，最终我们应该return的值始终是left
• 那么题目就很简单了，也就是二分法模板 + return left
• 代码如下：

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;		//确定最初的查找区间
        
        //左闭右闭
        while( left <= right )
        {
            //防止溢出
            int middle = left + ( (right - left) >> 1 );
            
            if( nums[middle] == target )
            {
                return middle;
            }
            else if( nums[middle] > target )
            {
                right = middle - 1;
            }
            else
            {
                left = middle + 1;
            }
        } 
        return left;
    }
};

• 时间复杂度：O（logn）

  空间复杂度：O（1）