LC 0033 [M] Search in Rotated Sorted Array - ALawliet/algorithms GitHub Wiki
https://www.youtube.com/watch?v=84a8fQp5hJA&ab_channel=Errichto
Notice that there is always a half of the array sorted, so we only need to see whether the target is in the sorted part or rotated part
find the first T greater than x
T T T T F F F
nums = [4,5,6,7,0,1,2]
the idea is to compare m with the first element to see if we are in the bigger or smaller half, find the correct half, then search that half
class Solution:
def search(self, A: List[int], T: int) -> int:
n = len(A)
l, r = 0, n - 1
while l <= r:
m = (l + r) // 2
if A[m] == T:
return m # found early
mid_biggerthan_start = A[m] >= A[0]
target_biggerthan_start = T >= A[0]
if mid_biggerthan_start == target_biggerthan_start: # check both the same, not (and), could be False == False
if A[m] < T:
l = m + 1
elif A[m] > T:
r = m - 1
else:
if mid_biggerthan_start:
l = m + 1
elif target_biggerthan_start:
r = m - 1
return -1