Core · Module 9 · Lesson 2 of 4

Lower and upper bounds

Instead of asking whether a value is present, ask where the first element that is at least x sits. That one question finds first and last occurrences, counts duplicates and gives insertion points, with no special cases.

ProAbout 13 minutes

By the end you can

Implement lower bound as a search for the first index where a condition becomes true
Find the first and last occurrence of a value, and count occurrences, with lower and upper bounds
Use insertion points to keep a sorted list sorted

Builds on Binary search without off-by-one bugs.

01 · A question first

A sorted array holds 1, 2, 2, 2, 3. A plain binary search for 2 might return index 1, 2 or 3, depending on where the halving happens to land. How do you reliably find the first 2, the last 2, or the place where a 4 should go?

Make a guess before you read on.

02 · The idea

Members only

Unlock the full lesson

This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.

What's inside

A better question
First true
Upper bound
Why the loop is correct
A worked example: the closest value
Library names
Searching records by a key
The general pattern

See plans Already a member? Sign in

03 · Practice

Practice · medium · LeetCodeFind first and last position of element in sorted arrayReturn the first and last index of a target in a sorted array with duplicates, using lower and upper bounds.Practice · easy · LeetCodeSearch insert positionReturn the index of a target in a sorted array, or where it would be inserted: the lower bound.Practice · medium · LeetCodeTime based key-value storeStore values with timestamps and answer 'value as of time t' queries with an upper-bound search per key.

Asked in interviews

Find the first and last position of a value in a sorted array

Something wrong with this lesson? Report a problem