Search in Rotated Sorted Array

1. Problem Description

Given a rotated sorted array whose rotation count is unknown in advance (for example, 0 1 2 4 5 6 7 may become 4 5 6 7 0 1 2). Search for the given target value in the array. If it exists, return its index; otherwise return -1. Assume there are no duplicate elements in the array.

2. Approach

Compared with Minimum Number in a Rotated Array, one problem finds the minimum value while this one finds a target value.

• Binary search
• First find the extreme point using Find Minimum in Rotated Sorted Array, then split the array into two sorted ranges and perform binary search

3. Implementation

3.1. Binary Search

func search(A []int, target int) int {
	if len(A) == 0 {
		return -1
	}

	left := 0
	right := len(A) - 1
	for left <= right {
		mid := (left + right) / 2
		if A[mid] == target {
			return mid
		} else if A[mid] >= A[left] {
			// Left side is sorted
			if A[mid] > target && A[left] <= target {
				right = mid - 1
			} else {
				left = mid + 1
			}
		} else {
			// Right side is sorted
			if A[mid] < target && A[right] >= target {
				left = mid + 1
			} else {
				right = mid - 1
			}

		}
	}
	return -1
}

3.2. Extreme Point

func search(nums []int, target int) int {
    minIndex := findMin(nums)
    ldx := bSearch(nums, 0, minIndex-1, target)
    if ldx != -1 {
        return ldx
    }
    rdx := bSearch(nums, minIndex, len(nums)-1, target)
    return rdx
}

func bSearch(nums[]int, left,right,target int) int {
    for left <= right {
        mid := left + (right-left) / 2
        if nums[mid] == target {
            return mid
        }else if nums[mid] > target {
            right = mid -1
        }else {
            left = mid +1
        }
    }
    return -1
}

func findMin(nums []int) int {
    left := 0
    right := len(nums)-1
    for left < right {
        mid := left + (right-left)/2
        if nums[mid] > nums[right] {
            left = mid + 1
        }else {
            right = mid
        }
    }
    return left
}
 

func search(nums []int, target int) int {
    minIdx := findMin(nums)
    idx := bSearch(nums, 0, minIdx-1,target)
    if idx != -1 {return idx}
    idx = bSearch(nums, minIdx, len(nums)-1,target)
    if idx != -1 {return idx}
    return -1
}

func bSearch(nums []int, left, right, target int) int {
    for left <= right {
        mid := left + (right-left)>>1
        if nums[mid] == target {
            return mid
        } else if nums[mid] < target {
            left = mid+1
        } else {
            right = mid-1
        }
    }
    return -1
}

func findMin(nums []int) int {
    left := 0
    right := len(nums)-1
    for left < right {
        mid := left + (right-left)>>1
        if nums[mid] > nums[right] {
            left=mid+1
        }else {
            right=mid
        }
    }
    return left
}

4. References

• Search for a Target in a Rotated Sorted Array - NowCoder
• Multiple Approaches - Search in Rotated Sorted Array - LeetCode