Search in Rotated Sorted Array II

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

    题解

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

    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.         if (A == null || A.length == 0) return false;
    9.         int lb = 0, ub = A.length - 1;
    10.         while (lb + 1 < ub) {
    11.             int mid = lb + (ub - lb) / 2;
    14.             if (A[mid] > A[lb]) {
    15.                 // case1: numbers between lb and mid are sorted
    16.                 if (A[lb] <= target && target <= A[mid]) {
    17.                     ub = mid;
    18.                 } else {
    19.                     lb = mid;
    20.                 }
    21.             } else if (A[mid] < A[lb]) {
    22.                 if (A[mid] <= target && target <= A[ub]) {
    23.                     lb = mid;
    24.                 } else {
    26.                 }
    27.             } else {
    28.                 // case3: A[mid] == target
    29.                 lb++;
    30.             }
    31.         }
    33.         if (target == A[lb] || target == A[ub]) {
    34.             return true;
    35.         }
    36.         return false;
    37. }

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