**Question:** Implement a search function for a sorted rotated array. Duplicates are allowed. Returning any one of the duplicates is acceptable.

**Answer:** We can do a binary search with some modified checks.

public int rotatedSearch(int[] values, int start, int end, int x){ if(values[start] == x){ return start; } else if(values[end] == x){ return end; } else if(end - start == 1) { return -1; } int middle = (start + end) / 2; if(values[start] <= values[middle]){ if(x <= values[middle] && x >= values[start]){ return rotatedSearch(values, start, middle, x); } else { return rotatedSearch(values, middle, end, x); } } else if(values[middle] <= values[end]){ if(x >= values[middle] && x <= values[end] ){ return rotatedSearch(values, middle, end, x); } else { return rotatedSearch(values, start, middle, x); } } else { return -1; } }

Like this question? Follow our feed and tweet it.

**If you're looking for some serious preparation for your interviews, I'd recommend this book written by a lead Google interviewer. It has 189 programming questions and solutions:**

## Leave a Reply

Using Gravatars in the comments - get your own and be recognized!

XHTML:These are some of the tags you can use:`<a href=""> <b> <blockquote> <code> <em> <i> <strike> <strong>`