首页 > 代码库 > (每日算法)LeetCode --- Search in Rotated Sorted Array(旋转数组的二分检索)

(每日算法)LeetCode --- Search in Rotated Sorted Array(旋转数组的二分检索)

<body>

Search in Rotated Sorted Array I && II

Leetcode


对有序数组进行二分查找(下面仅以非递减数组为例):

  1. int binarySort(int A[], int lo, int hi, int target)
  2. {
  3. while(lo <= hi)
  4. {
  5. int mid = lo + (hi - lo)/2;
  6. if(A[mid] == target)
  7. return mid;
  8. if(A[mid] < target)
  9. lo = mid + 1;
  10. else
  11. hi = mid - 1;
  12. }
  13. }

对有序的旋转数组进行二分查找:

eg. [7, 8, 9, 3, 4, 5, 6]

在数组中有且仅有一个 断点 (数字由大变小)。

还是通过折半来实现,关键是如有巧妙的绕过这个断点。

1.如果前半部分有序:

  • target 在该区间内,则 hi = mid - 1

  • 不在该区间内,则 lo = mid + 1

2.如果前半部分无序

  • target 在后半部分的有序区间内,则 lo = mid + 1

  • 不在该区间内, 则 hi = mid - 1

也就是说,我们优先考虑有序的部分。

  1. int search(int A[], int lo, int hi, int target)
  2. {
  3. while (lo <= hi)
  4. {
  5. int mid = (lo + hi) / 2;
  6. if (A[mid] == target)
  7. return mid;
  8. if (A[lo] <= A[mid])
  9. {
  10. if (A[lo] <= target && target < A[mid])
  11. hi = mid - 1;
  12. else
  13. lo = mid + 1;
  14. } else {
  15. if (A[mid] < target && target <= A[hi-1])
  16. lo = mid + 1;
  17. else
  18. hi = mid - 1;
  19. }
  20. }
  21. return -1;
  22. }

对包含重复元素的旋转数组进行二分查找:

允许重复元素,则上一题中如果A[m]>=A[l],那么[l,m]为递增序列的假设就不能成立了,比如[1,3,1,1,1]。

如果A[m]>=A[l]不能确定递增,那就把它拆分成两个条件:

  • 若A[m]>A[l],则区间[l,m]一定递增

  • 若A[m]==A[l]确定不了,那就l++,往下看一步即可。

  1. bool search(int A[], int lo, int hi, int target)
  2. {
  3. while (lo <= hi)
  4. {
  5. int mid = (lo + hi) / 2;
  6. if (A[mid] == target)
  7. return true;
  8. if (A[lo] < A[mid])
  9. {
  10. if (A[lo] <= target && target < A[mid])
  11. hi = mid - 1;
  12. else
  13. lo = mid + 1;
  14. } else if(A[lo] > A[mid]) {
  15. if (A[mid] < target && target <= A[hi-1])
  16. lo = mid + 1;
  17. else
  18. hi = mid - 1;
  19. }
  20. else
  21. lo++;
  22. }
  23. return false;
  24. }

(每日算法)LeetCode --- Search in Rotated Sorted Array(旋转数组的二分检索)