Search in Rotated Array

Medium

Python

def search(nums,target):
    l,r=0,len(nums)-1
    while l<=r:
        mid=(l+r)//2
        if nums[mid]==target: return mid
        if nums[l]<=nums[mid]:
            if nums[l]<=target<nums[mid]: r=mid-1
            else: l=mid+1
        else:
            if nums[mid]<target<=nums[r]: l=mid+1
            else: r=mid-1
    return -1

Java

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

Key Insight

Python chained comparison elegant. Java needs two conditions with &&.

Python → Java Differences

Python chained comparison a<=x<b
Java needs separate &&
Rotated search identical

Python

def search(nums,target):
    l,r=0,len(nums)-1
    while l<=r:
        mid=(l+r)//2
        if nums[mid]==target: return mid
        if nums[l]<=nums[mid]:
            if nums[l]<=target<nums[mid]: r=mid-1
            else: l=mid+1
        else:
            if nums[mid]<target<=nums[r]: l=mid+1
            else: r=mid-1
    return -1

Java

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

Algorithm Steps

1. Find sorted half
2. Check if target in sorted half

← Previous All Binary Search Next →