Follow up for "Search in Rotated Sorted Array":

What if

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.

**Understand the problem:**

The problem is an extension to the I. Since duplicates exist in the array, cutting the array into two halves will not work. Consider [1,3,1,1,1], target is 3, it will not find the targeted number.

**Solution:**

public class Solution { public boolean search(int[] A, int target) { if (A == null || A.length == 0) { return false; } int lo = 0; int hi = A.length - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; if (A[mid] == target) { return true; } if (A[lo] < A[mid]) { if (A[lo] <= target && target < A[mid]) { hi = mid - 1; } else { lo = mid + 1; } } else if (A[lo] > A[mid]) { if (A[mid] < target && target <= A[hi]) { lo = mid + 1; } else { hi = mid - 1; } } else { lo++; } } return false; } }

**Update on 9/29/14:**

If we directly use the original code from problem I, we will get errors. For example, for the input array [1, 3, 1, 1, 1], and target = 3. Now the situation is A[lo] = A[mid] = A[hi], so we are unable to say the first half is in ascending order.

**Code (Java):**

public class Solution { public boolean search(int[] A, int target) { if (A == null || A.length == 0) { return false; } int lo = 0; int hi = A.length - 1; while (lo + 1 < hi) { int mid = lo + (hi - lo) / 2; if (A[mid] == target) { return true; } if (A[lo] < A[mid]) { if (A[lo] <= target && target < A[mid]) { hi = mid; } else { lo = mid; } } else if (A[lo] > A[mid]) { if (A[mid] < target && target <= A[hi]) { lo = mid; } else { hi = mid; } } else { lo++; } } if (A[lo] == target || A[hi] == target) { return true; } return false; } }

The take-away message for this problem:

1. Figure out why the solution of problem 1 won't work. Take out an opposite example.

A = [3, 1, 2, 3, 3, 3, 3], where A[lo] == A[mid] == A[hi]

2. Analyze the time complexity in worst case, why it is O(n). Take an example.

A = [1, 1, 1, 1, 1, 1], where target = 2, then you need to iterate all elements of the array

A = [1, 1, 1, 1, 1, 0], where the target = 0, then you need to iterate all elements as well.

**Updates on 11/20/14:**

public class Solution { public boolean search(int[] A, int target) { if (A == null || A.length == 0) { return false; } int lo = 0; int hi = A.length - 1; while (lo + 1 < hi) { int mid = lo + (hi - lo) / 2; if (A[mid] == target) { return true; } if (A[lo] < A[mid]) { if (target >= A[lo] && target < A[mid]) { hi = mid; } else { lo = mid; } } else if (A[mid] < A[hi]) { if (target > A[mid] && target <= A[hi]) { lo = mid; } else { hi = mid; } } else { if (A[lo] == target) { return true; } lo++; } } if (A[lo] == target || A[hi] == target) { return true; } else { return false; } } }

The difference is to check A[mid] < A[hi] meaning right half is sorted.

The second difference is when we move the left pointer one step ahead, we need to check if it is equal to the target.

## No comments:

## Post a Comment