Search in Rotated Sorted Array II

Question

Problem Statement

Follow up for “Search in Rotated Sorted Array”:
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Write a function to determine if a given target is in the array.

题解

仔细分析此题和之前一题的不同之处，前一题我们利用A[start] < A[mid]这一关键信息，而在此题中由于有重复元素的存在，在A[start] == A[mid]时无法确定有序数组，此时只能依次递增start/递减end以缩小搜索范围，时间复杂度最差变为O(n)。

C++

  1. class Solution {
  2.     /**
  3.      * param A : an integer ratated sorted array and duplicates are allowed
  4.      * param target :  an integer to be search
  5.      * return : a boolean
  6.      */
  7. public:
  8.     bool search(vector<int> &A, int target) {
  9.         if (A.empty()) {
  10.             return false;
  11.         }
  13.         vector<int>::size_type start = 0;
  14.         vector<int>::size_type end = A.size() - 1;
  15.         vector<int>::size_type mid;
  17.         while (start + 1 < end) {
  18.             mid = start + (end - start) / 2;
  19.             if (target == A[mid]) {
  20.                 return true;
  21.             }
  22.             if (A[start] < A[mid]) {
  23.                 // situation 1, numbers between start and mid are sorted
  24.                 if (A[start] <= target && target < A[mid]) {
  25.                     end = mid;
  26.                 } else {
  27.                     start = mid;
  28.                 }
  29.             } else if (A[start] > A[mid]) {
  30.                 // situation 2, numbers between mid and end are sorted
  31.                 if (A[mid] < target && target <= A[end]) {
  32.                     start = mid;
  33.                 } else {
  34.                     end = mid;
  35.                 }
  36.             } else  {
  37.                 // increment start
  38.                 ++start;
  39.             }
  40.         }
  42.         if (A[start] == target || A[end] == target) {
  43.             return true;
  44.         }
  45.         return false;
  46.     }
  47. };

Java

  1. public class Solution {
  2.     /**
  3.      * param A : an integer ratated sorted array and duplicates are allowed
  4.      * param target :  an integer to be search
  5.      * return : a boolean
  6.      */
  7.     public boolean search(int[] A, int target) {
  8.         if (A == null || A.length == 0) return false;
  10.         int lb = 0, ub = A.length - 1;
  11.         while (lb + 1 < ub) {
  12.             int mid = lb + (ub - lb) / 2;
  13.             if (A[mid] == target) return true;
  15.             if (A[mid] > A[lb]) {
  16.                 // case1: numbers between lb and mid are sorted
  17.                 if (A[lb] <= target && target <= A[mid]) {
  18.                     ub = mid;
  19.                 } else {
  20.                     lb = mid;
  21.                 }
  22.             } else if (A[mid] < A[lb]) {
  23.                 // case2: numbers between mid and ub are sorted
  24.                 if (A[mid] <= target && target <= A[ub]) {
  25.                     lb = mid;
  26.                 } else {
  27.                     ub = mid;
  28.                 }
  29.             } else {
  30.                 // case3: A[mid] == target
  31.                 lb++;
  32.             }
  33.         }
  35.         if (target == A[lb] || target == A[ub]) {
  36.             return true;
  37.         }
  38.         return false;
  39.     }
  40. }

源码分析

在A[start] == A[mid]时递增start序号即可。

复杂度分析

最差情况下 O(n), 平均情况下 O(\log n).