First Occurrence in Sorted List
intermediateUp next
Binary Search Tree Explained
Understand binary search trees, search and insertion in Python, tree traversals, and why balanced trees keep operations fast.
Next lessonUp next
Understand binary search trees, search and insertion in Python, tree traversals, and why balanced trees keep operations fast.
Next lessonOutput will appear here...
You are given a list of integers sorted in ascending order. The list may contain repeated values.
Write a function first_occurrence(numbers, target) that returns the index of the first copy of target, or -1 if target isn't in the list. For example, in [1, 2, 2, 2, 3, 5] the first 2 is at index 1.
Tip
A loop from the left works, but because the list is sorted you can do much better. When binary search finds the target, don't stop: keep searching the left half in case an earlier copy exists.
The starter code reads the list on the first line and the target on the second.
No comments yet. Start the discussion.