首页 > itarticle > 35. search insert position

35. search insert position

admin 11月 13, 2020 0

题目描述

给一个有序数组和一个目标值，求比目标值小的个数。

题目分析

二分查找大于等于目标值的第一个数，然后算出比目标值小的个数。

代码

#include <iostream>
#include <vector>

class Solution {
public:
  int searchInsert(std::vector<int>& nums, int target) {
    return binarySearch(nums, target);
  }
  int binarySearch(std::vector<int>& nums, int target) {
    int l = 0;
    int r = nums.size() - 1;
    while (l <= r) {
      int mid = (l+r) >> 1;
      if (nums[mid] >= target) {
        r = mid - 1;
      } else {
        l = mid + 1;
      }
    }
    if (l <= nums.size()) {
      return l;
    }
    return -1;
  }
};

总结

1次AC。