First match in data of any order
No sorting needed. Also works on a sorted array; checks positions one by one.
Searching
Find a player with a given score, locate everyone with the same score, or find the lowest production rate that still meets a deadline. Learn to decide what a search should return.
We will start with a list of player scores: find one match, combine search techniques, and locate a whole group. Then we will search through possible answers and look at ways to speed up repeated queries.
You only need to know what an array and an index are. For an introduction to why a full pass grows as O(N), while repeatedly halving the work gives O(log N), see the examples in Big O.
Shared input
Choose a set of scores, then select a player whose score you want to find. Every array search uses this set. You can change it here or open Shared array in any example.
All player examples share this array. Changing the input resets them to the first step.
Select a player to search for their score. All players with that score will be highlighted together.
Target value:
Choose a value that is not in the array. Select again for another value.
Each cell shows a score and a class icon, with the index below. The current step identifies the character by name. Linear search uses the original order; the other array searches use a copy sorted by score. Sorting is not included in the counters. Choose up to 10 players, keep just one, or try an empty array. The workshop has its own settings.
Linear search
An arena match has ended, and we have the players’ scores. Each cell shows a score and an icon for the character’s class. The index below it is the player’s position in the array. We want to find one player with a particular score. If nobody has that score, the answer is “not found”; that is an ordinary outcome. N is the number of players, and target is the score we are looking for.
Let’s compare two algorithms. Linear search checks players one by one and works with scores in any order, including sorted order. Binary search roughly halves the remaining search area after each check. In this example, it needs the array to be sorted by score first.
Check elements one by one until a match is found.
Here we keep the players in registration order. We check the Warrior’s score, then the Mage’s, then the next player’s. We stop at the first match. Sorting the players by score would not change the algorithm: it would still check one position after another.
The number below each cell is the player’s index in the array. Counting starts at zero: the first player has index 0, the second has index 1, and the third has index 2. The algorithm returns the matching player’s index.
With sorted data, we can add an early stop. If we look for 15 in [5, 10, 20, 30], seeing 20 tells us that 15 cannot appear later. The code below does not include that check, so it works with any order. We will use this early stop in jump search later. Even with it, the worst case can still require a full pass.
About this implementation
This version returns the index of the first match, or notFound. It leaves the array unchanged.
All player examples share this array. Changing the input resets them to the first step.
Select a player to search for their score. All players with that score will be highlighted together.
Target value:
Choose a value that is not in the array. Select again for another value.
Positions visited0Target score21
The number in each cell is a score; the label below is its index. The icon identifies the character’s class. We search by score.
Registration order
Current player: —
Search window
Not determined yet
InspectingResultExcluded
Ready for the first step
Check elements one by one until a match is found.
Complexity
How to read these bounds
N is the array length. These bounds cover all passes made by the algorithm. They exclude input preparation and memory used to store animation frames. An empty array takes constant time.
The first player may be a match: O(1). A match only at the end, or no match at all, requires checking all N players: O(N). For this implementation, the bounds are the same for sorted and unsorted arrays: it only tests equality.
Best caseO(1)Worst caseO(N)Extra spaceO(1)
Try it. Choose Minimum at the end and keep at least two elements. Search for the first score in the array, then for 1, which appears last. Compare the visit counts. Then select Absent value.
Binary search
Use sorted order to rule out half of the remaining positions.
For this example, we prepare a copy of the array with players sorted by score. Inspect the middle: if the score is too low, continue on the right; if it is too high, continue on the left. Sorted order lets us rule out half the positions at once. A match ends the search. When several players share the target score, any one of them may be returned.
The array must be sorted by the field we compare. A list sorted by class name will not work for this search by score. In an unsorted array, the middle value tells us nothing about the values on either side: discarding a half could discard the player we need.
The returned index belongs to the sorted copy: the Rogue with 13 points now occupies a different position. We will call the remaining part of the array the search window.
Reading the search window
A square bracket includes a boundary; a round bracket excludes it. This applies at either end. In [1, 4), position 1 belongs to the window and position 4 does not: the included indices are 1, 2, and 3. These numbers are positions, not player scores.
Window [1, 4): indices 1, 2, and 3 are highlighted
The length of [left, right) is right − left. So [4, 4) is empty, while [0, N) covers the entire array. N is the position just after the last element; there is no element at that index.
About this implementation
The array must be sorted in ascending order. Sorting changes positions: the answer refers to the sorted copy shown here, not the original list.
All player examples share this array. Changing the input resets them to the first step.
Select a player to search for their score. All players with that score will be highlighted together.
Target value:
Choose a value that is not in the array. Select again for another value.
Positions visited0Target score21
The number in each cell is a score; the label below is its index. The icon identifies the character’s class. We search by score.
Sorted by score
Current player: —
Search window
Not determined yet
InspectingResultExcluded
Ready for the first step
Use sorted order to rule out half of the remaining positions.
Complexity
How to read these bounds
N is the array length. These bounds cover all passes made by the algorithm. They exclude input preparation and memory used to store animation frames. An empty array takes constant time.
A match at the first midpoint gives O(1). In the worst case, the number of visits grows as O(log N). The initial sort is accounted for separately.
Best caseO(1)Worst caseO(log N)Extra spaceO(1)
Try it. Choose All equal and keep at least two elements. Select any player, then run linear and binary search. Look at the character classes: why are both answers correct even though they identify different players?
Jump search
A search can use more than one technique. We can first narrow the search to a small part of the array, then choose how to examine it. Both examples below use a sorted array; they differ in how they locate that smaller part.
Skip whole blocks, then scan one block one position at a time.
Split the sorted player list into blocks of equal size. Inspect the last player in the first block. If even that player’s score is below the target, every other score in the block is too low as well. Jump to the end of the next block.
Stop jumping when a block’s last score is at least the target. Now check players within that block one by one. Return the index on a match. If a score is already above the target, stop without a match: the scores cannot decrease later.
This combines two techniques: first narrow the area in large steps, then inspect it closely. Ordinary binary search usually needs fewer array visits; jump search illustrates another way to use sorted order. We choose a block size near the square root of the number of elements: for 16 players, that is 4.
About this implementation
Scores must be sorted in ascending order. sqrt means square root; floor rounds down. The last block may be shorter. The scan can revisit a block’s final position, and the counter includes every visit.
All player examples share this array. Changing the input resets them to the first step.
Select a player to search for their score. All players with that score will be highlighted together.
Target value:
Choose a value that is not in the array. Select again for another value.
Positions visited0Target score21
The number in each cell is a score; the label below is its index. The icon identifies the character’s class. We search by score.
Sorted by score
Current player: —
Search window
Not determined yet
InspectingResultExcluded
Ready for the first step
Skip whole blocks, then scan one block one position at a time.
Complexity
How to read these bounds
N is the array length. These bounds cover all passes made by the algorithm. They exclude input preparation and memory used to store animation frames. An empty array takes constant time.
If the target is at the beginning of the first block, a constant number of visits is enough: O(1). In the worst case, we check the ends of about √N blocks, then up to √N elements within one block: O(√N). The initial sort is not included.
Best caseO(1)Worst caseO(√N)Extra spaceO(1)
Try it. Choose Minimum at the end, set 10 elements, and search for 8. Follow the search as it skips two blocks, then scans the third. Compare it with binary search on the same data.
Exponential search
After checking the first element, probe positions 1, 2, 4, 8… before switching to binary search.
Sometimes the target is near the beginning of a long sorted sequence. Instead of starting in the middle, begin with a small window and expand it. Stop when a probed value is at least the target, or when the array ends. Then use binary search within the window you have found.
The name comes from doubling the distance between probes. It does not mean the running time grows exponentially. Here the array’s length is known, and every read is checked against it. A source of unknown length would also need a safe way to detect its end.
About this implementation
The array must already be sorted. This version returns any exact match within the window it finds. Both phases can visit the same position; both visits count.
All player examples share this array. Changing the input resets them to the first step.
Select a player to search for their score. All players with that score will be highlighted together.
Target value:
Choose a value that is not in the array. Select again for another value.
Positions visited0Target score21
The number in each cell is a score; the label below is its index. The icon identifies the character’s class. We search by score.
Sorted by score
Current player: —
Search window
Not determined yet
InspectingResultExcluded
Ready for the first step
After checking the first element, probe positions 1, 2, 4, 8… before switching to binary search.
Complexity
How to read these bounds
N is the array length. These bounds cover all passes made by the algorithm. They exclude input preparation and memory used to store animation frames. An empty array takes constant time.
If the target’s lower bound is at position p, the two phases together take O(log(p + 2)) visits; the worst case is O(log(N + 1)). This can help near the beginning. Near the end, it may need more checks than ordinary binary search.
Best caseO(1)Worst caseO(log(N + 1))Extra spaceO(1)
Try it. Select a small score, then use Absent value to choose a value above every element. Find the step where the window stops expanding and starts shrinking.
First value at least the target
Suppose every player with exactly 21 points earns a reward. Finding one player is no longer enough. In sorted order, equal scores sit next to each other. We only need to find where the group begins and the position just after it.
Work through these three tasks in order. First find the left edge, then the right edge; together they describe the whole group and its size. If nobody has the target score, both bounds point to the same insertion position.
Find where the values below the target end.
We want the first position whose score is at least the target. This is the lower bound. If the middle score matches, keep searching on the left: an earlier player may have the same score.
For [10, 20, 20, 40], a target of 20 gives index 1. A target of 25 also has an answer: index 3, just before the player with 40 points. A bound identifies an insertion position; it does not by itself confirm an exact match. If every score is below the target, the answer is N.
About this implementation
The result is a position from 0 through N, inclusive. Before reading values[position], check that position < N. To confirm an exact match, also compare values[position] with the target.
All player examples share this array. Changing the input resets them to the first step.
Select a player to search for their score. All players with that score will be highlighted together.
Target value:
Choose a value that is not in the array. Select again for another value.
Positions visited0Target score21
The number in each cell is a score; the label below is its index. The icon identifies the character’s class. We search by score.
Sorted by score
Current player: —
Search window
Not determined yet
InspectingResultExcluded
Ready for the first step
Find where the values below the target end.
Complexity
How to read these bounds
N is the array length. These bounds cover all passes made by the algorithm. They exclude input preparation and memory used to store animation frames. An empty array takes constant time.
Each check roughly halves the window. For a nonempty array, the work grows logarithmically whether or not an exact match exists. Finding an insertion position takes O(log N), but actually inserting into an ordinary array may require shifting O(N) elements.
Best caseO(log N)Worst caseO(log N)Extra spaceO(1)
Try it. Use Absent value to choose a value below every element, then one above every element. Answers 0 and N are valid bounds, not errors.
First value above the target
Change one comparison to move past all equal values.
Now we want the first player whose score is strictly above the target. Equality needs different handling: a player with the target score still belongs to the group, so the search continues on the right.
For [10, 20, 20, 40] and a target of 20, the answer is index 3. This is the upper bound: the position after both players with 20 points. It is also where a new player could be inserted after those with the same score.
About this implementation
An answer of N means no element is strictly greater than the target. This is the end position, and it cannot be used to read an array element.
All player examples share this array. Changing the input resets them to the first step.
Select a player to search for their score. All players with that score will be highlighted together.
Target value:
Choose a value that is not in the array. Select again for another value.
Positions visited0Target score21
The number in each cell is a score; the label below is its index. The icon identifies the character’s class. We search by score.
Sorted by score
Current player: —
Search window
Not determined yet
InspectingResultExcluded
Ready for the first step
Change one comparison to move past all equal values.
Complexity
How to read these bounds
N is the array length. These bounds cover all passes made by the algorithm. They exclude input preparation and memory used to store animation frames. An empty array takes constant time.
The window still halves, so the bound for a nonempty array is O(log N). The difference from lower bound is how equality is handled; the rate of growth stays the same.
Best caseO(log N)Worst caseO(log N)Extra spaceO(1)
Try it. Compare the lower and upper bounds on an array of equal scores. Watch which way the search moves when the middle score equals the target.
All matching values
Two bounds describe the whole group without scanning it yet.
Combine the previous two answers. Players with the target score occupy [first, afterLast), and the group’s size is afterLast − first. The last player is at afterLast − 1, provided the group is not empty.
For [10, 20, 20, 40] and a target of 20, we get [1, 3): two players should receive a reward. For a target of 25, both bounds are 3, so no player qualifies. To actually give out the rewards, we still need to visit the group.
About this implementation
The helper runs twice: with strict = false it uses <, and with strict = true it uses <=. Each pass starts with the entire array, just like the previous two examples.
All player examples share this array. Changing the input resets them to the first step.
Select a player to search for their score. All players with that score will be highlighted together.
Target value:
Choose a value that is not in the array. Select again for another value.
Positions visited0Target score21
The number in each cell is a score; the label below is its index. The icon identifies the character’s class. We search by score.
Sorted by score
Current player: —
Search window
Not determined yet
InspectingResultExcluded
Ready for the first step
Two bounds describe the whole group without scanning it yet.
Complexity
How to read these bounds
N is the array length. These bounds cover all passes made by the algorithm. They exclude input preparation and memory used to store animation frames. An empty array takes constant time.
Two logarithmic searches still give O(log N). Storing the two bounds takes O(1) extra space. Reading or copying K matching elements afterwards adds O(K) work; their highlighting here is part of the visualization.
Best caseO(log N)Worst caseO(log N)Extra spaceO(1)
Try it. Choose All equal and select any player, then try Absent value. Compare the number of matches with the number of positions visited.
Keep track of the bounds
In the array examples, [left, right) includes the left boundary and excludes the right. Its length is right − left. The loop runs only while that length is positive, so the midpoint always refers to an existing element.
To discard the midpoint and everything before it, move to mid + 1. To discard the right part, set right = mid. Every iteration that does not return an answer must shrink the window. Setting left = mid can leave a one-element window unchanged forever.
Lower-bound search preserves two facts: values before left are too small, and values starting at right qualify. When the boundaries meet, we have found the transition. It may be N, even though values[N] does not exist.
The workshop uses a different convention: both ends of the answer range are included. There, left == right means one possibility remains. Check the boundary convention before reusing code from another example.
Smallest feasible answer
We can search through possible answers even when no array of those answers exists.
A workshop has four separate orders: 3, 6, 7, and 11 parts. Its machine makes rate parts per hour. Each order is allocated whole hours; unused time in its last hour cannot be passed to the next order. What is the lowest production rate that will meet the deadline?
At a rate of 4, the orders take 1 + 2 + 2 + 3 = 8 hours. Increasing the rate cannot increase the time needed. The possible rates therefore form a run of “too slow” answers followed only by “fast enough” answers. Binary search finds the boundary between them.
Here left and right are possible rates, and both boundaries are included. Keep a rate that works by moving right to rate. Exclude a rate that is too slow by moving left to rate + 1. The largest order gives a sufficient upper bound, as long as at least one hour is available for each order.
About this implementation
Order sizes are positive integers. Under these rules, four nonempty orders need at least four hours at any rate. A smaller time budget has no solution. The feasibility condition must be monotonic: once a rate works, every higher rate must work too.
Set how much time the workshop has to complete its four orders. Changing this setting resets only the workshop example. Player scores and the other examples keep their settings.
Parts in each order
Feasibility tests0Hours available8
Find the lowest production rate that meets the deadline. The possible rates are numbers, not players.
Possible production rates
Search window
Not determined yet
InspectingResultExcluded
Ready for the first step
We can search through possible answers even when no array of those answers exists.
Complexity
How to read these bounds
M is the number of orders; R is the size of the largest order. The time bound includes finding the maximum and every feasibility test. Memory used to store animation frames is excluded.
If there are fewer hours than orders, we can immediately report no solution in O(1). Otherwise, with M orders and a largest order of R parts, each test visits M orders and there are O(log R) tests. Including the initial maximum search and the case with only one possible rate gives O(M log(R + 1)) time and O(1) extra space. A fast outer search does not make its inner test free.
Best caseO(1)Worst caseO(M log(R + 1))Extra spaceO(1)
Try it. Start with 8 hours: the minimum rate is 4. Then try 4 hours and 3 hours. The last case has no solution, and the algorithm should say so.
Putting search to work
Changing the algorithm is only one way to speed up a search. Sometimes it helps more to prepare the data once, process queries together, or keep results that have already been calculated. Let’s explore those choices with our players.
Is it worth sorting just to search?
For one query on unsorted data, a linear pass is a sensible starting point. A comparison sort taking O(N log N), followed by an O(log N) search, has a higher asymptotic cost than one O(N) pass.
For Q queries on data that does not change, compare O(QN) with O(N log N + Q log N). Preparing the data once can pay off over many queries. The point at which it saves real time depends on the data, implementation, and hardware.
Account for updates too. Inserting into a sorted array may shift many elements. For frequent updates and exact-match queries, a hash table may be worth considering; queries over sorted ranges have different requirements.
Sorting changes indices as well. Keep an ID or original index alongside each value if you need to return to the original record. A position in the sorted view does not identify a position in the original list.
Find every player with 20 to 40 points
Bounds are useful for more than equal values. Take [10, 20, 20, 30, 40, 50] and reward everyone with 20 through 40 points, inclusive. The lower bound of 20 is index 1, and the upper bound of 40 is index 5. The qualifying players occupy [1, 5): their scores are 20, 20, 30, and 40.
To count the rewards, subtract the bounds: 5 − 1 = 4. To hand them out, visit only that group. A condition on scores has become a small part of the array. Notice that score 40 is included, while the right index boundary, 5, is excluded.
Avoid starting every search from scratch
Suppose three queries arrive after the match: does anyone have 20, 25, or 40 points? The scores are already sorted: [10, 20, 20, 30, 40, 50]. We could run three binary searches. For many queries that can be processed together, another technique is useful: two pointers.
One pointer moves through the scores; the other moves through the sorted queries. For 20, we skip 10 and find a match. For 25, continue from there: pass both twenties and stop at 30, so 25 is absent. For 40, continue until the match. Neither pointer moves backwards.
This processes two sorted lists in one combined pass. It is useful for a large batch; a single query usually does not justify scanning the list. Preparing the queries also takes work. If you reorder them, keep their original positions so the answers can be put back in the right order.
Build a convenient route to each record
Finding a player by ID and finding players with 20 to 40 points are different tasks. For IDs, we can build a hash table mapping ID → player. For score ranges, a separate sorted list of score → ID entries is useful: it finds the right group without rearranging the main player list.
This kind of auxiliary structure is called an index. It uses memory and must be updated when scores change. If a search key is expensive to calculate—for example, a rating based on match history—we can store the calculated ratings and search those. When the history changes, the stored ratings need to be recalculated too.
The key question is which work repeats. One search, thousands of queries on unchanged data, and a constantly changing leaderboard may call for different solutions. Compare the whole process: preparation, queries, and updates.
Start with the question
Any match in a sorted array
Compare, shrink the window, and stop on a match.
Skip blocks, then inspect one
Two phases on sorted data. A useful example of combining techniques, rather than a default replacement for binary search.
The target is likely near the beginning
Locate a window first; the extra probes do not always pay off.
First value ≥ target; insert before equals
The answer may be N. Check the bound before reading.
First value > target; insert after equals
Equal values belong to the left part being discarded.
Count or locate all equal values
Find two bounds; scan the range only if needed.
Smallest answer satisfying a monotonic condition
Include the cost of testing the condition in the complexity estimate.
Compare the work as well as the answers
Change the input or target through Shared array here; all player rows will update. The table shows each completed search, regardless of where its animation is paused. One visit means inspecting one chosen position, even if its value is used in several comparisons. Revisiting a position counts again. This is not a count of distinct elements, all operations, or elapsed time. The workshop counts complete feasibility tests separately; you can change its time budget below the table.
All player examples share this array. Changing the input resets them to the first step.
Select a player to search for their score. All players with that score will be highlighted together.
Target value:
Choose a value that is not in the array. Select again for another value.
| Method | Positions visited / feasibility tests | Result |
|---|---|---|
| Linear | — | — |
| Binary | — | — |
| Jump and scan | — | — |
| Exponential | — | — |
| Lower bound | — | — |
| Upper bound | — | — |
| Equal range | — | — |
| Search on the answer | — | — |
Linear search uses the original order; the other array searches use a sorted copy. Preparing that copy is not counted. An exact match, a bound, and a range answer different questions: their results are not interchangeable.
Set how much time the workshop has to complete its four orders. Changing this setting resets only the workshop example. Player scores and the other examples keep their settings.
Parts in each order
Try these before opening the explanations
We are looking for 15 in [5, 10, 20, 30]. When can a sequential search stop before the end?
Explanation
When it reaches 20—but only if the array is known to be sorted and the algorithm checks whether the current value exceeds the target. A search that tests only equality keeps going. Without sorting, 15 could appear after 20.
A block ends with 30 points, and we want 20. Can we skip the whole block?
Explanation
No. All we know is that the other values in this sorted block are at most 30; one of them may be 20. We can skip a whole block only if even its last value is below the target. Otherwise, scan within it.
What are the two bounds for a target of 4 in [2, 4, 4, 4, 9]?
Explanation
The lower bound is 1 and the upper bound is 4. The range [1, 4) contains three matches. Ordinary binary search may return index 1, 2, or 3.
Where would we insert 6 into [2, 4, 4, 9]? Does that mean we found 6?
Explanation
Both bounds are 3: the insertion position before 9. There is no exact match. The value at index 3 is 9, not 6.
What should happen with an empty array?
Explanation
An exact search returns notFound without reading any elements. Both bounds are 0, and the matching range is [0, 0). An insertion position exists even when there are no elements.
Can our binary search work on [2, 9, 4, 7] without preparation?
Explanation
No. Its rule for choosing a half depends on sorted order. The middle value cannot reliably tell us which half to keep. Sort a copy first, or use linear search.
Why can’t a rate of 3 complete orders of 3, 6, 7, and 11 parts within 8 hours?
Explanation
It needs ceil(3/3) + ceil(6/3) + ceil(7/3) + ceil(11/3) = 1 + 2 + 3 + 4 = 10 hours. A rate of 4 needs only eight hours, making 4 the first rate that works.