Challenge
Implement integer_search(items, target). The list items is sorted in non-decreasing order and contains integers; it may be empty and may contain duplicates. Return the Boolean True if target is present, otherwise False. Do not mutate the input. Aim for O(log n) time and constant auxiliary space.
Target complexity: O(log n)
Return values are checked by type. Use the exact function name. Print output is not your answer. Tests have time and memory limits.
Public examples
Example 1
Arguments
[[1, 3, 5, 7, 9, 11, 13, 15, 17, 19], 5]
Expected return
True
Example 2
Arguments
[[2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40], 41]
Expected return
False
Hint
Discard half of the remaining search interval on each step.
The worked solution unlocks after completion, or with Premium access.