Learn
B2.4.2 | LINEAR AND BINARY SEARCH
01 | RETRIEVE THE RIGHT ITEM
A library program knows the book ID a student requested, but it still needs to find the matching stored record. A search algorithm systematically examines data to locate a target, or establish that it is absent.
The target is the value we seek. The collection contains candidate items. Our first functions return the zero-based index of a matching item, or -1 when no match exists. The caller can use a valid index to retrieve the item.
We will construct and trace linear and binary search in Python, with equivalent Java methods. Both algorithms retrieve data, but they have different prerequisites and search strategies.
02 | VALUES AND INDEXES ARE DIFFERENT
| Index | Stored value |
|---|---|
| 0 | 18 |
| 1 | 7 |
| 2 | 25 |
| 3 | 4 |
| 4 | 12 |
The target 25 is stored at index 2. Returning 2 means “the match is at this position”; returning 25 would instead return the value itself. Be explicit about the function’s result.
Python lists and Java arrays use zero-based indexes: the first index is 0 and the last is length − 1. A human-facing “third item” therefore has index 2.
We choose -1 as a not-found result because it is not a valid non-negative array index. Python does allow negative indexing, so the caller must test the result before using it as an index.
03 | LINEAR SEARCH: CHECK IN ORDER
Imagine looking through an unsorted pile of cards. Start with the first card, compare its value with the target, then move to the next card if it is not a match. Stop at a match or after the final card.
This is linear search, also called sequential search. It does not require sorted data. It can search numbers, names or records as long as we have a suitable equality test.
For [18, 7, 25, 4, 12] and target 25: compare 18, then 7, then 25. The third comparison succeeds, so return index 2 without examining 4 or 12.
04 | CONSTRUCT THE LINEAR SEARCH FUNCTION
def linear_search(values, target):
for index in range(len(values)):
if values[index] == target:
return index
return -1
values = [18, 7, 25, 4, 12]
print(linear_search(values, 25))
print(linear_search(values, 9))
The outputs are 2 and -1. range(len(values)) supplies the valid indexes. Each iteration compares one item with target, and return index exits the whole function immediately on a match.
The final return -1 is outside the loop. It is reached only after every candidate has failed. If it were inside the loop after the if, the function would wrongly report failure immediately after the first nonmatch.
The input list is not changed. For an empty list the loop has no iterations, so the function safely returns -1.
05 | TRACE A SUCCESSFUL LINEAR SEARCH
| Comparison | index | values[index] | Equals 25? | Action |
|---|---|---|---|---|
| 1 | 0 | 18 | False | Continue |
| 2 | 1 | 7 | False | Continue |
| 3 | 2 | 25 | True | Return 2 |
Record the index and the stored value in separate columns. They describe different information. There are three inspected items; no comparisons are made after returning.
A trace follows the exact code. Do not continue filling rows for indexes 3 and 4 merely because those indexes exist.
06 | TRACE FAILURE ALL THE WAY TO THE END
| Comparison | index | Stored value | Equals 9? |
|---|---|---|---|
| 1 | 0 | 18 | False |
| 2 | 1 | 7 | False |
| 3 | 2 | 25 | False |
| 4 | 3 | 4 | False |
| 5 | 4 | 12 | False |
After the fifth failed comparison, the range is exhausted and the function returns -1. A nonmatch at one position does not prove absence from the whole list.
For n items, an unsuccessful linear search checks n equality comparisons. A target in the first position needs only one. An empty list needs none.
07 | DUPLICATES: WHAT DOES FOUND MEAN?
def linear_search(values, target):
for index in range(len(values)):
if values[index] == target:
return index
return -1
print(linear_search([7, 4, 7, 9], 7))
The result is 0 because this version stops at the first match from the left. It does not count occurrences or return every matching position.
A search contract should state whether it returns any match, the first match, the last match or all matches. These are different requirements.
To obtain every matching index with a linear scan, append matching indexes to a result list and return that list after the loop. Avoid an early return when more matches are required.
08 | RETRIEVE A RECORD USING A KEY
def find_book(books, wanted_id):
for index in range(len(books)):
if books[index]["id"] == wanted_id:
return index
return -1
books = [{"id": 18, "title": "Robots"},
{"id": 7, "title": "Networks"},
{"id": 25, "title": "Databases"}]
position = find_book(books, 7)
if position != -1:
print(books[position]["title"])
else:
print("Book not found")
The output is Networks. A search key is the field used to identify or compare candidate records; here it is id. The returned position gives access to the whole matching record.
Check position != -1 before indexing. In Python, books[-1] would retrieve the last book, creating a dangerous-looking success when the target was actually absent.
This example assumes every record has an id and that IDs are unique. Names and titles may be duplicated, so choose a key matching the retrieval requirement.
09 | BINARY SEARCH NEEDS ORDER
If cards are sorted, we can inspect a middle card. When that value is too small, every earlier card is also too small. We can discard that entire side without checking each item.
Binary search repeatedly narrows a sorted candidate interval by comparing the target with its middle value. Our version assumes ascending numerical order and constant-time indexed access.
For an unsorted collection, the direction deduction is invalid. A target can lie in the half that the algorithm wrongly discards. Checking a middle value alone does not make a search correct.
10 | LOW AND HIGH ARE INCLUSIVE INDEXES
We keep two boundaries: low is the smallest remaining candidate index; high is the largest. Both are included in the active interval. Initially low = 0 and high = len(values) − 1.
For eight values, the initial interval is indexes 0 through 7. It contains eight candidates, not seven. When low == high, one candidate remains and must still be checked.
When low > high, the interval is empty. That is how the loop detects that no candidate remains. The condition must be low <= high for this inclusive-boundary implementation.
11 | CALCULATE THE MIDDLE INDEX
low = 0
high = 7
middle = (low + high) // 2
print(middle)
The result is 3. Integer division // keeps the whole-number quotient, so the algorithm chooses the lower of the two middle indexes when the interval length is even.
middle is an index, not the middle stored value. In [3, 7, 11, 15, 19, 23, 27, 31], index 3 stores 15. Compare 15 with the target; do not compare the index 3 with the target.
An upper-middle convention can also work with compatible updates. Trace the convention actually used by the supplied code.
12 | UPDATE PAST THE CHECKED MIDDLE
| Comparison | What sorted order establishes | Update |
|---|---|---|
| values[middle] == target | Match found | Return middle |
| values[middle] < target | Middle and all earlier candidates are too small | low = middle + 1 |
| values[middle] > target | Middle and all later candidates are too large | high = middle − 1 |
The +1 and −1 exclude the already checked nonmatching middle. Setting low = middle or high = middle can leave the same interval unchanged, causing a loop that never finishes.
Only one boundary changes after a nonmatch. Keep the other boundary, because its side can still contain the target.
The invariant is: if the target is present and not yet found, at least one matching position remains within the inclusive interval. Correct updates preserve this fact.
13 | CONSTRUCT ITERATIVE BINARY SEARCH
def binary_search(values, target):
low = 0
high = len(values) - 1
while low <= high:
middle = (low + high) // 2
if values[middle] == target:
return middle
elif values[middle] < target:
low = middle + 1
else:
high = middle - 1
return -1
values = [3, 7, 11, 15, 19, 23, 27, 31]
print(binary_search(values, 27))
print(binary_search(values, 20))
The outputs are 6 and -1. The while loop tests whether any candidate remains. A match returns immediately; a nonmatch moves one boundary beyond middle. Failure is returned only after the interval becomes empty.
This code assumes the collection is already sorted ascending. It does not validate or sort the data itself. The function returns an index in the supplied collection, which is not necessarily an index in any earlier unsorted version.
14 | TRACE TARGET 27: FOLLOW EVERY BOUNDARY
| Probe | low before | high before | middle | Value | Decision / next state |
|---|---|---|---|---|---|
| 1 | 0 | 7 | 3 | 15 | 15 < 27; low becomes 4 |
| 2 | 4 | 7 | 5 | 23 | 23 < 27; low becomes 6 |
| 3 | 6 | 7 | 6 | 27 | Match; return 6 |
The active indexes shrink from 0–7 to 4–7 to 6–7. The third probe finds the target. A probe is one inspected midpoint; the if/elif code may perform more than one comparison during a probe.
The table labels low and high before the probe so you can use them to calculate middle. The decision column records the update for the next probe.
15 | TRACE TARGET 20: AN EMPTY INTERVAL
| Probe | low before | high before | middle | Value | Decision / next state |
|---|---|---|---|---|---|
| 1 | 0 | 7 | 3 | 15 | Too small; low = 4 |
| 2 | 4 | 7 | 5 | 23 | Too large; high = 4 |
| 3 | 4 | 4 | 4 | 19 | Too small; low = 5 |
The next test is low <= high, or 5 <= 4, which is false. There is no fourth midpoint access. The function returns -1.
Notice the third probe: low == high was still a valid one-item interval. Changing the loop to low < high would incorrectly skip such a final candidate.
16 | INTERACTIVE: STEP THROUGH BOTH SEARCHES
Enter up to 12 comma-separated integers from −99 to 99, or leave the list empty. Linear search preserves the supplied order. Binary search requires ascending order; this activity rejects an unsorted list instead of silently sorting it.
Key: CURRENT = inspected item; ACTIVE = remaining candidates; DISCARDED = excluded; FOUND = match. Labels accompany the colours.
Predict the next inspected index before clicking. Try 27, 20, the first value, the final value, one item, an empty list and duplicate values. Changing an input restarts the trace, so old results cannot be mistaken for results for the new data.
17 | TEST EMPTY AND ONE-ITEM COLLECTIONS
| Data | Target | Expected result | Reason |
|---|---|---|---|
| [] | 7 | -1 | No candidates |
| [7] | 7 | 0 | Single candidate matches |
| [7] | 3 | -1 | Single candidate too large |
| [7] | 9 | -1 | Single candidate too small |
| [3, 7] | 7 | 1 | Second item must remain reachable |
For an empty binary-search input, high starts at -1 while low is 0. The first condition is false, so the algorithm never indexes the empty collection.
These tests expose off-by-one errors more directly than a single large example. Also test absent targets below the minimum, between stored values and above the maximum.
18 | BINARY SEARCH AND DUPLICATE VALUES
For [2, 4, 4, 4, 8] and target 4, our algorithm initially checks middle index 2 and returns 2. It finds a matching occurrence, but does not promise the first occurrence at index 1.
This differs from the shown left-to-right linear search, which returns the first matching index. If duplicates exist, the algorithms can both be correct while returning different matching indexes under an “any match” contract.
If the task requires the first matching index, modify the algorithm explicitly rather than assuming binary search already guarantees it.
19 | EXTENSION: FIND THE FIRST DUPLICATE
def first_binary_match(values, target):
low = 0
high = len(values) - 1
result = -1
while low <= high:
middle = (low + high) // 2
if values[middle] >= target:
if values[middle] == target:
result = middle
high = middle - 1
else:
low = middle + 1
return result
print(first_binary_match([2, 4, 4, 4, 8], 4))
This returns 1. A match is saved in result, but the search continues to its left to look for an earlier match. If no earlier match exists, the saved result survives until return.
Every iteration still removes about half the remaining interval, so the worst-case search time remains O(log n) under the same assumptions. This is an extension of the basic algorithm, not a requirement to change every search.
20 | JAVA: COMPLETE LINEAR AND BINARY METHODS
public class SearchExample {
static int linearSearch(int[] values, int target) {
for (int index = 0; index < values.length; index++) {
if (values[index] == target) {
return index;
}
}
return -1;
}
static int binarySearch(int[] values, int target) {
int low = 0;
int high = values.length - 1;
while (low <= high) {
int middle = low + (high - low) / 2;
if (values[middle] == target) {
return middle;
} else if (values[middle] < target) {
low = middle + 1;
} else {
high = middle - 1;
}
}
return -1;
}
public static void main(String[] args) {
int[] values = {3, 7, 11, 15, 19, 23, 27, 31};
System.out.println(linearSearch(values, 27));
System.out.println(binarySearch(values, 27));
}
}
Both methods print index 6. Java integer division produces the required midpoint for these non-negative differences. low + (high − low) / 2 avoids adding two potentially large indexes before division.
Python integers do not have the same fixed-width overflow issue, so the earlier (low + high) // 2 is appropriate there. The boundary convention and updates are otherwise equivalent.
21 | COMPARING EFFICIENCY FAIRLY
| Property | Shown linear search | Shown iterative binary search |
|---|---|---|
| Order required | No | Ascending |
| Best-case search time | O(1) | O(1) |
| Worst-case search time | O(n) | O(log n) |
| Auxiliary search space | O(1) | O(1) |
| Duplicate policy | First match from left | Any match reached |
Let n be the number of items and assume constant-time equality, ordering and indexed access. An unsuccessful linear search inspects n items. Binary search reduces the interval by about half after each nonmatch.
For the shown midpoint convention and n >= 1, at most floor(log₂ n) + 1 midpoint probes are needed. Do not equate probes with every individual relational comparison in the source.
For 1,024 items, an unsuccessful linear search inspects all 1,024; the binary search uses at most 11 probes. A favourable binary target can be found in the first probe.
22 | INCLUDE SORTING AND DATA MAINTENANCE
Sorting an unsorted collection just to perform one small search may cost more than a single scan. If sorting uses O(n log n) time, a sort followed by one O(log n) search is dominated by the sort.
For many searches of a mostly unchanged collection, sorting once and reusing the order can be worthwhile. Frequent insertions or updates may add costs to preserving sorted order.
Sorting also changes positions. Keep each key attached to its record, and return positions in the collection actually searched. Sorting a separate list of keys without preserving record associations can retrieve the wrong data.
Binary search relies on efficient midpoint access. A linked list does not provide the same constant-time indexed access assumed in this lesson.
23 | WHY THE ALGORITHMS TERMINATE
Linear search moves to the next valid index after a nonmatch. The finite range is eventually exhausted. Binary search discards the inspected midpoint and one side after each nonmatch. Its nonempty interval therefore strictly shrinks.
The binary-search invariant says that an existing target remains among the candidates until found. Sorted order justifies discarding a side; the +1 and −1 updates ensure progress. Both correctness and termination matter.
If a program uses low = middle on a two-item interval, it can repeatedly choose the same lower middle. This is why copying a boundary update without its matching interval convention is risky.
24 | CONSTRUCT A SEARCH FROM A SCENARIO
A school stores student records in arrival order and wants one record for an exact student ID. A linear search is straightforward because the data is not ordered by ID. Compare each record’s ID, return its position on a match, and report failure only after the full scan.
A second system maintains a large array sorted by unique student ID and performs many lookups. Binary search is appropriate under the indexed-access assumption. Compare the middle record’s ID, not the whole record or its position, and retrieve the matching record after a valid result.
Before coding, specify the data representation, ordering, equality rule, returned result, duplicate policy and absent-target behaviour. These choices determine the correct algorithm interface.
25 | BUILD A TRACE THAT EXPLAINS THE PROCESS
For linear search, record the inspected index, value, equality result and action. For binary search, record low and high before the probe, calculated middle, middle value, comparison outcome and next boundary update.
Show the final result separately from intermediate candidates. A midpoint examined during a failed search is not a retrieved record. When low becomes greater than high, record the false loop test and return -1.
Use the command word Trace by following the supplied algorithm exactly. If the question instead says Construct, supply a complete algorithm with initialization, conditions, progress, success and failure paths.
26 | COMMON ERRORS TO AVOID
| Error | Consequence | Correction |
|---|---|---|
| Return failure inside first nonmatch | Later values never checked | Return -1 after the loop |
| Search unsorted data with binary search | Wrong half can be discarded | Meet sorted-data precondition |
| Compare middle with target | Compares an index rather than data | Use values[middle] |
| Use low < high with inclusive bounds | Final candidate can be skipped | Use low <= high |
| Set low = middle after too-small value | May repeat the same interval | Use middle + 1 |
| Use -1 as a Python index unchecked | Returns last item on failure | Test result before retrieval |
| Expect first duplicate from basic binary search | May return another match | State or implement duplicate policy |
A good solution makes the search contract clear and tests the boundaries that are easiest to get wrong. Use the activities to justify each update rather than memorize the code without its meaning.