33. Search in Rotated Sorted Array

search-in-rotated-sorted-array.go

// https://leetcode.com/problems/search-in-rotated-sorted-array/
//
// Time:  O(log n)
// Space: O(1)
//
// n = number of elements in the array

// .................... //

func search(nums []int, target int) int {
    n := len(nums)
    last := nums[n-1]

    lo, hi := 0, n-1
    for lo <= hi {
        mi := lo + (hi-lo)/2

        if nums[mi] > last {
            lo = mi + 1
        } else {
            hi = mi - 1
        }
    }

    min := lo
    if target > last {
        lo, hi = 0, min
    } else {
        lo, hi = min, n-1
    }

    for lo <= hi {
        mi := lo + (hi-lo)/2

        if nums[mi] == target {
            return mi
        }

        if nums[mi] > target {
            hi = mi - 1
        } else {
            lo = mi + 1
        }
    }

    return -1
}