[关闭]
@kuailezhishang 2014-12-10T21:24:42.000000Z 字数 1091 阅读 1544

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.如果前半部分有序:

2.如果前半部分无序

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

  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]不能确定递增,那就把它拆分成两个条件:

  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. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注