Description

We have a rotated increasing array (4,5,6,7,0,1,2) find the target value in O(log(n))
?
4 cases use binary search once we find the sorted segment that it is in.

• left < middle and it is in it.
• left < middle and it is NOT in it.
• middle < right and it is in it.
• middle < right and its NOT in it.

Runtime

O(log(n))

Pseudocode

using l, r in two pointer
while l <= r:
    m = (l + r) // 2
    if nums[m] == target: return m
    if nums[l] <= nums[m]:              # left half sorted
        if nums[l] <= target < nums[m]: # in it
            r = m - 1
        else:                           # not in it
            l = m + 1
    else:                               # right half sorted
        if nums[m] < target <= nums[r]: # in it
            l = m + 1
        else:                           # not in it
            r = m - 1
return -1