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

3. Implementation

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
}

4. References

• Search for a Target in a Rotated Sorted Array - NowCoder