Binary Search
Intermediate
The problem
Given a list arr of integers sorted in ascending order and an integer target, return the index of target in arr, or -1 if it is not there. Your solution must run in O(log n) time, so scanning the list one element at a time will not do.
Implement solve(arr, target). The signature and docstring are already in the editor.
Constraints
arris sorted ascending and has no duplicates; it may be empty.targetmay be smaller or larger than every element.
Hints
Hint 1
Keep two indices, lo and hi, that bound the part of the list that could still hold target. Look at the middle element each round.
Hint 2
If the middle element is too small, target can only be to its right, so move lo past it. If it is too big, move hi before it. Stop when lo > hi.
Keywords
dsa
Python
Run your code to see results
No results yet
Run your code to check it against the examples, or submit to run every test.