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

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

2024-08-07 07:55:26   217人阅读

<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(旋转数组的二分检索)


联系
我们