81. Search in Rotated Sorted Array II

search-in-rotated-sorted-array-ii.go

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

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

func search(nums []int, target int) bool {
    n := len(nums)
    lo, hi := 0, n-1

    for lo <= hi {
        mi := lo + (hi-lo)/2
        if nums[mi] == target {
            return true
        }

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

    return false
}