LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 要求 O(log n) 时间复杂度，数组有序，因此应当使用二分搜索
• 对于旋转过的数组，中间值的左右侧，必然有一侧是升序排列的

$$$@@@ // $$$ 和 @@@ 为旋转后有序的两部分

$$$ 中的任何元素，其左侧都位于 $$$ 中，必然有序
@@@ 中的任何元素，其右侧都位于 @@@ 中，必然有序

• 检查目标值是否位于升序排列的一侧，以此来缩小范围

class Solution {
 public:
  int search(vector<int>& nums, int target) {
    if (empty(nums)) {
      return -1;
    }
    int l = 0;
    int r = size(nums);
    while (l != r) {
      int m = l + (r - l) / 2;
      if (target == nums[m]) {
        return m;
      }
      if (nums[m] >= nums[l]) {                       // 左侧升序
        if (target < nums[m] && target >= nums[l]) {  // 位于左侧
          r = m;
        } else {
          l = m + 1;
        }
      } else {  // 左侧不为升序则右侧一定为升序
        if (target > nums[m] && target <= nums[r - 1]) {  // 位于右侧
          l = m + 1;
        } else {
          r = m;
        }
      }
    }
    return -1;
  }
};