14. 二分查找

275. H 指数 II

 int hIndex(vector<int> &citations) {
    int length = citations.size();
    int left = 0, right = length - 1;
    while (left <= right) {
      int mid = left + ((right - left) >> 1);
      if (citations[mid] >= length - mid) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    }
    return length - left;
  }

35. 搜索插入位置

class Solution {
public:
    int searchInsert(vector<int> &nums, int target) {
    if (nums.empty()) {
      return -1;
    }
    int left = 0, right = nums.size() - 1;
    int index = -1;
    while (left <= right) {
      int mid = left + ((right - left) >> 1);
      if (nums[mid] >= target) {
        index = mid;
        right = mid - 1;
      } else if (nums[mid] < target) {
        left = mid + 1;
      } else {
        return mid;
      }
    }
      return index == -1 ? nums.size() : index;
  }
};

977. 有序数组的平方

class Solution {
public:
  vector<int> sortedSquares(vector<int> &nums) {
    int n = nums.size();
    vector<int> res(n);
    int left = 0, right = n - 1;
    int index=n-1;
    while (left <= right) {
      if (abs(nums[left]) < abs(nums[right])) {
        res[index--] = nums[right] * nums[right];
        right--;
      } else {
        res[index--] = nums[left] * nums[left];
        left++;
      }
    }
    return res;
  }
};