What must be true of a list before binary search can be applied to it reliably?

It must contain no duplicate values

Its length must be a power of 2

Assertion (A): Linear search can be used on a list whose elements are in no particular order. Reason (R): In the worst case, linear search compares the key with every element of the list.

Both A and R are true, but R is not the correct explanation of A

Both A and R are true, and R is the correct explanation of A

Both A and R are true, but R is not the correct explanation of A

Searching

Finding a roll number in an unsorted register means reading it name by name; finding a word in a dictionary means opening it near the middle and discarding half the book at every step. Those are the two searching methods of the syllabus — linear search and binary search — and the difference between them is the difference between checking everything and using order. This chapter traces both, counts how many comparisons each needs in the best and worst cases, and closes with hashing, which aims to find an element in a single step. Expect questions that ask for the elements examined in a binary search, in order, and for worst-case counts.

Linear Search

Linear search, also called sequential search, compares the key with each element of the list in turn, starting from the first, until it finds a match or reaches the end. It makes no assumption about order, so it works on an unsorted list. If the key is the first element it needs just one comparison — the best case. If the key is the last element, or is not in the list at all, it compares the key with all n elements — the worst case. Its running time therefore grows in proportion to n: it is a linear algorithm.

A linear search that returns the position of the first match, or −1 if there is none. print(search([5, 3, 5, 8], 5), search([5, 3, 5, 8], 6)) prints 0 -1 — the second 5 is never reached:
def search(L, key):
for i in range(len(L)):
if L[i] == key:
return i
return -1

Binary Search

Binary search works only on a sorted list. It keeps two markers, first and last, around the part still to be searched, and repeatedly examines the middle element, mid = (first + last) // 2. If the middle element equals the key, the search succeeds. If the key is smaller, it can only lie in the left half, so last becomes mid − 1; if larger, first becomes mid + 1. When first passes last, the part to search is empty and the key is not present. Each comparison discards about half of what remains, so the number of comparisons grows only with the number of times n can be halved: in the worst case floor(log₂ n) + 1 — 4 for 15 elements, 5 for 31, 7 for 100, 10 for 1,000.

Binary search for 23 in [3, 8, 12, 17, 23, 31, 40]
first	last	mid	Element at mid	Decision
0	6	3	17	23 > 17, so first = 4
4	6	5	31	23 < 31, so last = 4
4	4	4	23	found at index 4

⚠️ Integer division picks the left middle

With first = 4 and last = 5, mid is (4 + 5) // 2 = 4, not 4.5 and not 5. In an even-length range the left of the two middle elements is examined, and a trace that rounds up will name the wrong elements from that point on.

Linear and binary search compared
Feature	Linear search	Binary search
List must be sorted?	No	Yes
Best case	1 comparison (first element)	1 comparison (middle element)
Worst case, n elements	n comparisons	floor(log₂ n) + 1 comparisons
Growth	linear in n	logarithmic in n

Search by Hashing

Hashing tries to find an element without comparing it against others at all. A hash function computes, from the element itself, the position in a hash table where it should be stored. A simple one is the remainder method: h(element) = element % size of the table. With a table of 10 slots, 34 goes to slot 4, 16 to slot 6 and 93 to slot 3; to search for 93, compute 93 % 10 = 3 and look in slot 3 directly. When two elements produce the same slot — 34 and 54 both give 4 — that is a collision, which has to be resolved by some further rule; a hash function that never produces a collision for a given set of elements is a perfect hash function.

Key takeaways

Linear search checks elements one by one, works on unsorted lists, and needs 1 comparison at best and n at worst.
Binary search needs a sorted list: compare with the middle, then keep only the half that can hold the key.
mid = (first + last) // 2; a smaller key sets last = mid − 1, a larger key sets first = mid + 1, and first > last means not found.
Binary search needs at most floor(log₂ n) + 1 comparisons: 5 for 31 elements, 10 for 1,000.
Hashing computes an element's slot directly, e.g. element % table size; two elements in one slot is a collision.

Practice questions (8)

Attempt each one before opening the answer. Every explanation names the tempting wrong option as well as the right one, because that is where marks are lost.

Binary search is used to find 23 in the sorted list [3, 8, 12, 17, 23, 31, 40], with mid = (first + last) // 2. Which elements are compared with 23, in order?
1. 17, 23
2. 17, 31, 23
3. 3, 8, 12, 17, 23
4. 17, 40, 31, 23
Show answer
Answer: B — 17, 31, 23
First mid is index 3, element 17; 23 is larger, so first = 4. Now mid = (4 + 6) // 2 = 5, element 31; 23 is smaller, so last = 4. Then mid = 4, element 23 — found after three comparisons. 17, 23 skips the middle of the right half and jumps straight to the key. The five-element sequence is what a linear search would do, and nothing in binary search ever looks at the last element first.
What does this code print?
def search(L, key):
for i in range(len(L)):
if L[i] == key:
return i
return -1
print(search([5, 3, 5, 8], 5), search([5, 3, 5, 8], 6))
1. 2 -1
2. 1 -1
3. 0 None
4. 0 -1
Show answer
Answer: D — 0 -1
The loop returns as soon as it finds the first match, which for 5 is at index 0; the 5 at index 2 is never reached. For 6 the loop ends without a match and the function returns -1. Answering 2 assumes the search continues to the last match, 1 counts positions from 1, and None would be returned only if the final return -1 were missing.
What must be true of a list before binary search can be applied to it reliably?
1. It must be sorted
2. It must contain no duplicate values
3. Its length must be a power of 2
4. It must hold integers only
Show answer
Answer: A — It must be sorted
Discarding a half is only safe if every element on one side of the middle is smaller and every element on the other side larger, and that is what sorting guarantees. Duplicates do not stop the method; it simply finds one of the equal values. Any length works, since integer division picks a middle every time, and strings sorted alphabetically can be searched just as well as numbers.
What is the maximum number of comparisons binary search needs to decide whether a key is present in a sorted list of 31 elements?
1. 31
2. 16
3. 5
4. 6
Show answer
Answer: C — 5
Each comparison leaves at most half of the remaining elements: 31, then 15, 7, 3 and 1, so after the fifth comparison nothing is left to examine — floor(log₂ 31) + 1 = 5. Thirty-one is the worst case of a linear search, the method that ignores order. 16 halves only once, and 6 adds an extra step that a range of 31 never needs.
What is printed by the following code?
L = [2, 4, 6, 8, 10, 12, 14]
first, last, steps = 0, len(L) - 1, 0
key = 5
while first <= last:
mid = (first + last) // 2
steps += 1
if L[mid] == key:
break
elif key < L[mid]:
last = mid - 1
else:
first = mid + 1
print(steps)
1. 2
2. 3
3. 7
4. 4
Show answer
Answer: B — 3
Step 1: mid = 3, element 8; 5 < 8, so last = 2. Step 2: mid = 1, element 4; 5 > 4, so first = 2. Step 3: mid = 2, element 6; 5 < 6, so last = 1. Now first (2) exceeds last (1), the loop ends with the key absent, and steps is 3. Stopping at 2 forgets that the range [2, 2] still has to be examined, and 7 counts every element as a linear search would.
A linear search is run on a list of n elements for a key that is not in the list. How many comparisons does it make?
1. 1
2. n / 2
3. n
4. about log₂ n
Show answer
Answer: C — n
Linear search can only conclude that the key is absent after comparing it with every element, so an unsuccessful search costs all n comparisons — the worst case. One comparison is the best case, when the key happens to be first. n / 2 is the average for a key that is present, and log₂ n belongs to binary search on a sorted list.
Assertion (A): Linear search can be used on a list whose elements are in no particular order. Reason (R): In the worst case, linear search compares the key with every element of the list.
1. Both A and R are true, and R is the correct explanation of A
2. Both A and R are true, but R is not the correct explanation of A
3. A is true, but R is false
4. A is false, but R is true
Show answer
Answer: B — Both A and R are true, but R is not the correct explanation of A
Both statements are true, but R describes the cost of linear search, not why it works on unordered data. It works on any list because it never uses order to skip an element — every element is examined in turn until a match is found. Choosing "R explains A" links two true facts that happen to be about the same method; the paper sets exactly this pairing to test whether the link is real.
Using linear search from the first element, how many comparisons are needed to find 9 in the list [4, 7, 9, 2]?
1. 2
2. 4
3. 1
4. 3
Show answer
Answer: D — 3
The key is compared with 4, then 7, then 9, where it matches and the search stops: three comparisons. Two is the zero-based index of 9, a position rather than a count. Four would be needed only if the key were last or absent, and one only if it were the first element.