Search in Rotated Sorted Array II | Leetcode

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: Use a modified form of binary search. The key is that we cannot say for sure whether a portion of the array is sorted or not if the first number is equal to the last number, i.e. nums[lo] == nums[hi]. Therefore, we have to say that the first number must be less than the last number (i.e. nums[lo] < nums[hi]) before we are sure that it is sorted. When we are not sure the portion is sorted, just reuse binary search on each half of the array portion from lo to hi.

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