Lesson guide
What this Python exercise practices
Find the first occurrence with binary search is a beginner practice lesson that focuses on dsa, problem patterns, edge cases. It is designed to be solved in about 10 minutes with examples, starter code, and test feedback.
Prerequisites
- Python functions
- Loops
- Lists
- Basic edge cases
Difficulty and time
- Level
- Beginner
- Estimated time
- 10 minutes
Related public exercises
Summary
Using binary search, find the first (leftmost) index of a target value in a sorted array with possible duplicates.
Problem statement
Given a sorted list of integers (ascending) that may contain duplicates, implement a function first_occurrence(arr, target) which returns the index of the first (leftmost) occurrence of target. If the target is not present, return -1. The solution must use binary search and run in O(log n) time.
Task
Implement first_occurrence(arr, target) that returns the index of the first occurrence of target or -1 if not present.
Examples
First occurrence among duplicates
Input
first_occurrence([1, 2, 2, 2, 3], 2)
Output
1
Explanation
The first (leftmost) 2 is at index 1.
Input format
A sorted list of integers 'arr' and an integer 'target' passed to first_occurrence(arr, target).
Output format
An integer index of the first occurrence (0-based) or -1 if not found.
Constraints
0 <= len(arr) <= 10^5. Time complexity O(log n).
Samples
Sample input 0
first_occurrence([1, 1, 2, 2, 3], 1)
Sample output 0
0
Explanation 0
First occurrence of 1 is at index 0.
AI assistant
Ask me anything!
Need help? I can explain the core idea behind this problem, review your current code, and give targeted hints. Use “Teach Theory” for the concept, “Get AI hint” for a quick scaffold nudge, or ask a specific question below.
Chat history is temporary and will not be saved.
Free preview includes 1 Teach Theory response and 1 AI hint per unlocked preview lesson.