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.
Solution:
1. public class Solution {
2. public boolean search(int[] A, int target) {
3. return bsearch(A, target, 0, A.length - 1);
4. }
5. 6. private boolean bsearch(int[] A, int target, int lo, int hi) {
7. if (lo > hi) {
8. return false;
9. }
10. 11. int mid = lo + (hi - lo) / 2;
12. 13. if (A[mid] == target) {
14. return true;
15. }
16. 17. if (A[lo] < A[mid]) {
18. if (target >= A[lo] && target < A[mid]) {
19. return bsearch(A, target, lo, mid - 1);
20. } else {
21. return bsearch(A, target, mid + 1, hi);
22. }
23. } else if (A[lo] > A[mid]) {
24. if (target > A[mid] && target <= A[hi]) {
25. return bsearch(A, target, mid + 1, hi);
26. } else {
27. return bsearch(A, target, lo, mid - 1);
28. }
29. } else {
30. return bsearch(A, target, lo + 1, hi);
31. }
32. }
33. }