Find the first occurrence with binary search

Easy

≈ 10 minute session

Back to curriculum

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

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

Explanation 0

First occurrence of 1 is at index 0.

Code editor

Loading editor…

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.

03:44 PM

Free preview includes 1 Teach Theory response and 1 AI hint on each of the first 3 lessons in this module.