题目

image.png556

思路

  • 此题的关键在于，需要清楚，左边的和右边的，哪边是可以放弃的。
  • 如果nums[mid] < nums[right],说明[mid, right]必然有序
  • 如果nums[mid] > nums[right],说明[left, mid - 1]必然有序
  • 利用有序区间的端点值，判断是不是在序列当中，如果在，那么放弃掉无序的一边，如果不在，放弃掉有序的一边。

  • 此题的二段性，体现在，一段里面包含target，另外一段不包含target

    代码

    1. class Solution {
    2. public:
    3.   int search(vector<int>& nums, int target) {
    4.       // 如果 nums[mid] < nums[right],说明[mid, right]必然有序
    5.       // 如果 nums[mid] > nums[right],说明[left, mid - 1]必然有序
    6.       // 利用有序区间的端点值，判断是不是在序列当中，如果在，那么放弃掉无序的一边，如果不在，放弃掉有序的一边
    7.       // 此题的二段性，体现在，一段里面包含target，另外一段不包含target
    9.       int n = nums.size();
    10.       int left = 0, right = n - 1;
    11.       while (left < right) {
    12.           int mid = (left + right + 1) / 2;
    13.           // 如果右边有序
    14.           if (nums[mid] < nums[right]) {
    15.               // 如果右边符合要求，选择右边
    16.               if (nums[mid] <= target && target <= nums[right]) {
    17.                   left = mid;
    18.               // 如果右边不符合要求，选择左边
    19.               } else {
    20.                   right = mid - 1;
    21.               }
    22.           // 如果左边有序
    23.           } else {
    24.               // 如果左边符合条件
    25.               if (nums[left] <= target && target <= nums[mid - 1]) {
    26.                   right = mid - 1;
    27.               // 如果左边不符合条件
    28.               } else {
    29.                   left = mid;
    30.               }
    31.           }
    32.       }
    34.       if (nums[left] == target) {
    35.           return left;
    36.       } else {
    37.           return -1;
    38.       }
    39.   }
    40. };

    mid向上取整图示（mid在右区间）
    image.png

  1. class Solution {
  2. public:
  3.     int search(vector<int>& nums, int target) {
  4.         // 如果 nums[mid] < nums[right],说明[mid, right]必然有序
  5.         // 如果 nums[mid] > nums[right],说明[left, mid - 1]必然有序
  6.         // 利用有序区间的端点值，判断是不是在序列当中，如果在，那么放弃掉无序的一边，如果不在，放弃掉有序的一边
  7.         // 此题的二段性，体现在，一段里面包含target，另外一段不包含target
  9.         int n = nums.size();
  10.         int left = 0, right = n - 1;
  11.         while (left < right) {
  12.             int mid = (left + right) / 2;
  13.             // 如果右边有序
  14.             if (nums[mid] < nums[right]) {
  15.                 // 如果右边符合要求，选择右边
  16.                 if (nums[mid + 1] <= target && target <= nums[right]) {
  17.                     left = mid + 1;
  18.                 // 如果右边不符合要求，选择左边
  19.                 } else {
  20.                     right = mid;
  21.                 }
  22.             // 如果左边有序
  23.             } else {
  24.                 // 如果左边符合条件
  25.                 if (nums[left] <= target && target <= nums[mid]) {
  26.                     right = mid;
  27.                 // 如果左边不符合条件
  28.                 } else {
  29.                     left = mid + 1;
  30.                 }
  31.             }
  32.         }
  34.         if (nums[left] == target) {
  35.             return left;
  36.         } else {
  37.             return -1;
  38.         }
  39.     }
  40. };

mid向下取整图示（mid在左区间）
image.png