81.search-in-rotated-sorted-array-ii.md

81. Search in Rotated Sorted Array II

TODO: Add notes.

fun search(nums: IntArray, target: Int): Boolean {
    var left = 0
    var right = nums.size - 1
    while (left <= right) {
        val middle = left + (right - left) / 2
        if (nums[middle] == target) return true
        // The key difference between this and 33. Search in Rotated Sorted Array.
        if (nums[left] == nums[middle]) {
            left++
            continue
        }
        if (nums[left] <= nums[middle]) {
            if (target in nums[left]..nums[middle]) {
                right = middle - 1
            } else {
                left = middle + 1
            }
        } else {
            if (target in nums[middle]..nums[right]) {
                left = middle + 1
            } else {
                right = middle - 1
            }
        }
    }
    return false
}