解析

//! log(n),log(n)->二分查找log(n)次，函数递归栈log(n)大小
class Solution {
 public:
  int searchInsert(vector<int> &nums, int target) {
    return binarySearch(nums, 0, nums.size() - 1, target);
  }
  int binarySearch(vector<int> nums, int left, int right, int target) {
    if (left > right) {
      return left;
    }
    int mid = (left + right) / 2;
    if (nums[mid] == target) {
      return mid;
    } else if (nums[mid] > target) {
      return binarySearch(nums, left, mid - 1, target);
    } else {
      return binarySearch(nums, mid + 1, right, target);
    }
  }
};

//! log(n),1->二分查找log(n)次，常数空间
class Solution {
 public:
  int searchInsert(vector<int> &nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left <= right) {
      int mid = (left + right) / 2;
      if (nums[mid] < target) {
        left = mid + 1;
      } else if (nums[mid] > target) {
        right = mid - 1;
      } else {
        return mid;
      }
    }
    return left;
  }
};