Search in Rotated Sorted Array

Java

class Solution {
    public int search(int[] nums, int target) {
        if(nums.length == 0) return -1;
        int l = 0;
        int r = nums.length - 1;
        while((l+1) < r){
            int mid = (l+ r) / 2;
            if(nums[mid] > nums[l]) {
                if(nums[mid] > target && nums[l] <= target){
                    r = mid;
                } else {
                    l = mid;
                }
            } else {
                if(nums[mid] < target && nums[r] >= target){
                    l = mid;
                } else {
                    r = mid;
                }
            }
        }
        if(nums[l] == target) return l;
        if(nums[r] == target) return r;
        return -1;
    }
}

Python

class Solution:
# @param {integer[]} nums
# @param {integer} target
# @return {integer}
def search(self, nums, target):
    if not nums:
        return -1
    return self.binarySearch(nums, target, 0, len(nums)-1)
    
def binarySearch(self, nums, target, start, end):
    if end < start:
        return -1
    mid = (start+end)/2
    if nums[mid] == target:
        return mid
    if nums[start] <= target < nums[mid]: # left side is sorted and has target
        return self.binarySearch(nums, target, start, mid-1)
    elif nums[mid] < target <= nums[end]: # right side is sorted and has target
        return self.binarySearch(nums, target, mid+1, end)
    elif nums[mid] > nums[end]: # right side is pivoted
        return self.binarySearch(nums, target, mid+1, end)
    else: # left side is pivoted
        return self.binarySearch(nums, target, start, mid-1)