#63 Search in Rotated Sorted Array II

题目描述：

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.

Have you met this question in a real interview?  Yes Example

Given [1, 1, 0, 1, 1, 1] and target = 0, return true. Given [1, 1, 1, 1, 1, 1] and target = 0, return false.

题目思路：

这题和#62一样，不同的是数组中可能有重复数字出现。所以在第一次寻找最小值的index时，我先把A[l] == A[l + 1]和A[r] == A[r - 1]的情况过滤掉，再用binary search找最小值的位置。

Mycode（AC = 50ms）：

class Solution { /** * param A : an integer ratated sorted array and duplicates are allowed * param target : an integer to be search * return : a boolean */ public: bool search(vector<int> &A, int target) { // write your code here if (A.size() == 0) return false; // find index of minimum number in A int l = 0, r = A.size() - 1, sidx = -1; while (l + 1 < r) { while (l + 1 < r && A[l] == A[l + 1]) { l++; } while (l + 1 < r && A[r] == A[r - 1]) { r--; } int mid = (l + r) / 2; if (A[mid] <= A[l] || A[mid] <= A[r]) { r = mid; } else { l = mid; } //cout << l << " " << r << endl; } sidx = A[l] <= A[r]? l : r; // get normally sorted numbers indexed from // start ~ end int start = sidx, end = sidx + A.size() - 1; while (start <= end) { int mid = (start + end) / 2; if (A[mid % A.size()] == target) { return true; } else if (A[mid % A.size()] < target) { start = mid + 1; } else { end = mid - 1; } } return false; } };