Valley Bottom

A valley-shaped array is an array of integers such that:

it can be split into a non-empty prefix and a non-empty suffix,
the prefix is sorted in decreasing order,
the suffix is sorted in increasing order,
all the elements are unique.

Given a valley-shaped array, arr, return the smallest value.

Example 1:

Input: arr = [6, 5, 4, 7, 9]
Output: 4

Example 2:

Input: arr = [5, 6, 7]
Output: 5 (The prefix sorted in decreasing order is just [5])

Example 3:

Input: arr = [7, 6, 5]
Output: 5 (The suffix sorted in increasing order is just [5])

1def valleyBottom(arr: List[int]) -> int:
2    l, r = 0, len(arr) - 1
3    
4    while l < r:
5        mid = (l + r) // 2
6        if arr[mid] < arr[mid + 1]:
7            # Increasing part (or bottom), min is at mid or left
8            r = mid
9        else:
10            # Decreasing part, min is to the right
11            l = mid + 1
12            
13    return arr[l]

Search in Rotated Sorted Array

l

6

0

5

1

mid

4

2

7

3

r

9

4

Step 1 / 4

Step 1:

Initialize l=0, r=4. Compute mid=2.

Pointers: l=0, mid=2, r=4

Focus: select @ [2]