You are given an array arr of n integers and a single integer x. Your job is to find out where x lives in the array.
Return the index of the first occurrence of x in arr. If x is not present at all, return -1.
The array is not sorted, so you have no shortcuts — x could be hiding anywhere. Indices are 0-based: the first element is at index 0.
Input: arr = [1, 2, 3, 4], x = 3 Output: 2 3 sits at index 2, so we return 2.
Input: arr = [10, 8, 30, 4, 5], x = 5 Output: 4 5 is the last element, at index 4.
Input: arr = [10, 8, 30], x = 6 Output: -1 6 never appears, so we return -1.
- 1 <= arr.size <= 10^6 - 0 <= arr[i] <= 10^6 - 0 <= x <= 10^5
Linear search is the first algorithm most people invent on their own, but it carries a real lesson: when data has no structure, O(n) is not just easy — it's the best you can do. The only refinement is knowing when to stop, which turns a fixed full pass into a best-case constant-time lookup.
-1 to mean "not found", so the missing case needs no special path.Given an array arr (not sorted) and a value x, return the index of the first occurrence of x. If x is absent, return -1. Indices are 0-based.
Worked example — arr = [1, 2, 3, 4], x = 3
index: 0 1 2 3
value: 1 2 3 4
▲ found at index 2 → return 2
“Is the array sorted?”
No — that's the crux. A sorted array would unlock binary search; an unsorted one forces a full scan.
“Can the array be empty?”
If so, no element matches and the answer is -1.
“What if x appears more than once?”
Return the first (leftmost) match. Scanning left to right and returning early handles this for free.
“What if x isn't present at all?”
Return the -1 sentinel.
“Do I return the index or a boolean found/not-found?”
The index (or -1). Worth confirming, since it changes what you return on a match.
“How large can the array be?”
Up to 10^6. A single O(n) pass is comfortable; anything asymptotically slower would not be.
A couple of checks first.
Is the array sorted, or unsorted? That decides whether binary search is on the table.
If x appears multiple times, do I return the first index?
And I return -1 when it's absent?
Since it's unsorted, I'll scan left to right and return the moment I find x.
Binary search works only because a sorted array lets you rule out half the elements at each step. With no order, x could sit anywhere, so any correct method must be able to inspect every element. That makes O(n) a genuine lower bound, not just a first attempt.
Because you scan left to right, the first index where arr[i] == x is by definition the earliest occurrence. There is nothing to gain by reading further, so return right away. Worst case (absent or last) is still O(n), but a lucky early match finishes in O(1).
It's tempting to sort so you can binary-search — but sorting costs O(n log n), already worse than one O(n) scan, and it also destroys the original indices you were asked to return. Only sort if you'll run many searches on the same array.
| Full scan | Early exit | |
|---|---|---|
| Idea | Read every element, keep first match | Return on the first match |
| Time (worst) | O(n) | O(n) |
| Time (best) | O(n) | O(1) |
| Space | O(1) | O(1) |
The full code for both is in the Approaches selector below.
Key takeaway
On unsorted data, a single O(n) scan is optimal — you can't rule out any element without looking at it. Returning the instant you find x keeps the worst case at O(n) while making the best case O(1): the "stop the moment the answer is known" idea that also powers short-circuit && / ||.