Ceil in a Sorted Array

You are given a sorted array arr and an integer x. Your task is to find the ceil of x — the smallest element in arr that is greater than or equal to x — and return its 0-based index.

If no element in arr is greater than or equal to x, return -1.

Note: if the ceil value appears multiple times, return the index of its first occurrence.

Hints

· Stuck? Reveal one nudge at a time.

The array is sorted — what does one comparison against a middle element tell you about everything on either side of it?

Every element is either < x or >= x, and the sorted order groups them into two zones. You are hunting for the index where the second zone begins.

Binary search with a twist: when arr[mid] >= x, don't stop — record mid as a candidate and continue searching left with hi = mid - 1. The last recorded candidate is the first occurrence.

Common doubts

The smallest element of arr that is greater than or equal to x. If x itself is present, x is its own ceil. You return the index of that element, not the value.

Multiple copies of the ceil value can exist (e.g. [1, 1, 2] with x = 0 — both 1s qualify). The problem pins down a unique answer by asking for the leftmost index, which the sorted order makes well-defined.

Only when x is strictly greater than the last (largest) element — then nothing in the array is >= x, so no ceil exists.

Almost. The lower-bound index is exactly the insert position that keeps arr sorted (inserting before duplicates). The only difference is the out-of-range case: insert position would be n, while this problem maps it to -1.

Interview follow-ups

· What an interviewer asks next.

Mirror the loop: when arr[mid] <= x, record mid and search right (lo = mid + 1); otherwise search left. It is the same boundary hunt approached from the other side.

Run lower bound twice: first occurrence of v and first occurrence of v + 1 (or first index with element > v). The difference of the two indices is the count — two O(log n) searches.

Plain lower bound breaks because the two-zone structure is displaced. First binary search for the rotation point (the minimum), then run the ceil search in the correct half — still O(log n) overall.

Fun facts

The record-and-go-left loop you wrote here is exactly what C++ ships as std::lower_bound, Python as bisect.bisect_left, and Go as sort.SearchInts — one of the few interview algorithms that exists verbatim in every major standard library.
The 'find the first element that satisfies a condition' pattern — binary search on answer — powers far harder problems too: first bad version, allocating minimum pages, and capacity-to-ship-packages all reuse this identical loop with a fancier condition.
A subtle detail worth bragging about in interviews: writing mid = lo + (hi - lo) / 2 instead of (lo + hi) / 2 avoids integer overflow when lo and hi are both huge — a real bug that lived in Java's standard library binary search for nine years.

Asked at

AmazonMicrosoftAdobeOraclePaytm

Frequently Sometimes Occasionally

Example 1

Input: arr = [1, 2, 8, 10, 11, 12, 19], x = 5
Output: 2
The smallest element >= 5 is 8, at index 2.

Example 2

Input: arr = [1, 2, 8, 10, 11, 12, 19], x = 20
Output: -1
No element is >= 20, so there is no ceil.

Example 3

Input: arr = [1, 1, 2, 8, 10, 11, 12, 19], x = 0
Output: 0
The smallest element >= 0 is 1, which appears at indices 0 and 1. The first occurrence is index 0.

Constraints

- 1 <= arr.size <= 10^6 - 1 <= arr[i] <= 10^6 - 0 <= x <= 10^6 - arr is sorted in non-decreasing order

Ceil in a Sorted Array is the friendliest doorway into the single most reusable binary-search variant: lower bound — find the first element that satisfies a condition. Master the boundary-hunting idea here and dozens of harder problems collapse into the same six lines of code.

Prerequisites

Before you start

· Concepts used directly in the solution.

Sorted arrays. Order is information — once elements are sorted, one comparison tells you about an entire half of the array.

Binary search. The classic halving loop with lo and hi pointers; here we adapt it to find a boundary instead of an exact match.

0-based indexing. The answer is an index, not a value — off-by-one care is the whole game.

Understand the problem

In plain English: scan the sorted array and report where the first element >= x sits. Formally: return the smallest index i such that arr[i] >= x, or -1 if no such index exists. Because arr is sorted, the first element >= x is automatically the smallest element >= x — and automatically the first occurrence of that value.

Worked example — arr = [1, 2, 8, 10, 11, 12, 19], x = 5

index:   0   1   2    3    4    5    6
arr:   [ 1,  2,  8,  10,  11,  12,  19 ]
         <x  <x  ✓ first element >= 5
answer: index 2 (value 8)

Clarifying questions

Asking two or three sharp questions before coding shows an interviewer you think about contracts, not just code.

Questions to ask first

· Signals seniority before you write a line of code.

Input validity

“Is the array guaranteed to be sorted in non-decreasing order?”

Yes — and this guarantee is the entire reason binary search applies. If it could be unsorted, only a linear scan would be correct.

“Can the array contain duplicate values?”

Yes. That is why the statement pins down the tie-break: return the index of the first occurrence of the ceil value.

Edge cases

“What if x is larger than every element?”

There is no ceil — return -1. This is the only failure case.

“What if x is smaller than or equal to every element?”

The answer is index 0 — the very first element is already >= x.

“What about a single-element array?”

Return 0 if that element is >= x, otherwise -1. A great sanity test for the loop bounds.

Constraints and scale

“How large can the array be?”

Up to 10^6 elements. A linear scan still passes, but binary search in O(log n) is what the sorted input is inviting you to do — about 20 steps instead of a million.

The ideal opening — say it like this

Before I code, let me confirm a few things.

The array is sorted non-decreasing and may contain duplicates — so for ties I return the first occurrence, correct?

If x exceeds every element I return -1, and since it is sorted and can be up to a million elements, I will binary search for the boundary rather than scan linearly.

Key observations

1Aha

A sorted array splits into two clean zones around x

Every element is either < x or >= x, and because the array is sorted, all the < x elements sit on the left and all the >= x elements sit on the right — two contiguous zones with one boundary between them. The answer is simply the index where the second zone begins.

arr = [ 1   2 | 8   10   11   12   19 ]   x = 5
        < x  |  >= x
             ^ the boundary — index 2 is the answer

2Aha

One comparison at mid discards half the array

Probe the middle element. If arr[mid] >= x, then mid is a candidate answer — but a better (smaller) index might exist to its left, so record it and search left. If arr[mid] < x, then mid and everything left of it are in the wrong zone — search right. Either way, half the array vanishes per step.

3Aha

First occurrence comes for free

Because a match makes us keep looking left, the search never settles for a later duplicate. When the loop ends, the recorded candidate is the leftmost index with arr[i] >= x — exactly the first-occurrence rule the problem demands. No post-processing needed.

Brute force vs optimal

	Linear scan	Binary search
Time	O(n)	O(log n)
Space	O(1)	O(1)
Steps at n = 10^6	~1,000,000	~20

Both full implementations, with traces and pitfalls, are in the Approaches selector below.

Summary

Key takeaway

This is the lower bound pattern: binary search for the first index whose element satisfies a condition (arr[i] >= x) by recording every match and continuing left. Any problem phrased as find the first / smallest element that… over sorted data is this exact loop with a different condition.

lo = 0, hi = n - 1, ans = -1
while lo <= hi:
    mid = lo + (hi - lo) / 2
    if arr[mid] >= x:  ans = mid; hi = mid - 1   # candidate — look left
    else:              lo = mid + 1              # too small — look right
return ans