【leetcode】35. 搜索插入位置

题目内容

搜索插入位置

思路分析

本题其实就是C++的lower_bound函数的弱化版。

方法一：C++ STL

直接调lower_bound函数。

方法二：自己实现

直接按照模板来写，不同之处是如果没找到target的话需要返回插入的位置（left指针）。

代码

#include <vector>
#include <math.h>
#include <limits.h>

using namespace std;

// 二分 C++ STL
// 时间复杂度O(logn)
// 空间复杂度O(1)
class Solution1 {
public:
    int searchInsert(vector<int>& nums, int target) {
       return lower_bound(nums.begin(), nums.end(), target) - nums.begin();
    }
};

// 二分 自己实现
// 时间复杂度O(logn)
// 空间复杂度O(1)
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
       int left = 0, right = nums.size() - 1;
       
       while (left <= right) {
          int mid = left + (right - left) / 2;
          if (nums[mid] == target) {
             return mid;
          } else if (nums[mid] > target) {
             right = mid - 1;
          } else if (nums[mid] < target) {
             left = mid + 1;
          }
       }

       return left; // 由于本题的特殊性，这一点和模板不一样
    }
};

int main() {
   Solution s;
   vector<int> input{ 1,3,5,6 };
   int target = 5;
   int result = s.searchInsert(input, target);
   int a = 0;
}

收获

巩固了下二分查找