Loading...
Loading...
Loading...
A sorted list that may contain repeated values was rotated, for example 4 5 5 1 1 2 3. Read a target and print yes if it is in the list and no otherwise. Use binary search, and accept that repeated values can make the worst case slower.
Example 1
Input
7 4 5 5 1 1 2 3 1
Output
yes
Example 2
Input
7 4 5 5 1 1 2 3 6
Output
no
Try the problem first. Open one hint at a time.
When a[lo], a[mid] and a[hi] are all equal you cannot tell which half is sorted, so move both ends in by one.
Otherwise find the sorted half as before and check whether the target lies in it.
Write your Python code, run it on the examples and submit it to hidden tests.
Solve in the editor