Searching

Written and reviewed by Rohit Singh, Computer Science & Commerce faculty at UniDrill (MCA, Osmania University · 6 years teaching). Based on NCERT Computer Science Class XII, Chapter 6.

How does a phone find one contact among a billion?

Open a dictionary and you do not start at page one. You flip to the middle, see that the word you want comes later, and throw away the first half in one move. A computer can do the same with data, and the trick is so strong that a sorted list of about a billion records can be searched in roughly 30 steps instead of a billion. This chapter is about three ways of searching a list, what each one demands from your data, and how much work each one does.

Searching means locating a particular element, called the key, in a collection. The result tells you whether the key is present and, if it is, where.

Linear search: check every element in order

Linear search (also called sequential or serial search) compares the key with each element one by one, from the first towards the last. It stops with success at the first match, or with failure after the whole list has been checked. It needs no order at all, so it is the right tool for a small, unordered list.

The algorithm sets index = 0, repeats while index < n, compares numList[index] with the key, prints index + 1 as the position when they match, and otherwise increments the index. Notice the last step: the position reported to the user is index + 1, because people count from 1 while Python counts from 0.

Worked example: tracing linear search. Let numList = [8, -4, 7, 17, 0, 2, 19], so n = 7, and search for the key 17.

The key is found after 4 comparisons at index 3, so the program reports position 4. The common slip is to report 3.

How much work linear search does depends only on where the key sits. The same seven numbers show all three cases.

Failing is as expensive as finding the last element, because only after looking at everything can you say "not here". The time grows in step with the size of the list, which is why linear search becomes slow for large lists.

Program: linear search as a function. The function returns the position (index plus one) or None.

Calling it on the list from the trace:

If the list holds duplicates, such as [42, -2, 32, 8, 17, 19, 42, 13, 8, 44], searching for 8 returns position 4. The loop returns as soon as it meets the first match, so later copies are never reached.

Pause and predict: In the list [7, -1, 11, 32, 17, 19, 23, 29, 31, 37, 43], how many comparisons does linear search make to find the key 43?

Check your answer: 11. The key 43 is the last of the 11 elements, so every element has to be compared. This is the worst case, $n$ comparisons.

Binary search: halve the problem every time

Binary search uses the order of a sorted list. You compare the key with the middle element and one of three things happens: it matches (done), the middle is greater than the key (the key can only be in the first half), or the middle is smaller than the key (the key can only be in the second half). Either way, half the list is gone after a single comparison, and you repeat on what is left. The list may be sorted in ascending or descending order, and text works too if it is in alphabetical order.

The reason it needs a sorted list is the sentence "the key can only be in the first half". That is true only if everything before the middle is smaller. In an unsorted list the sentence is false and you would throw away the very half that holds the key.

The algorithm keeps three markers, first = 0, last = n - 1 and mid = (first + last) // 2, and repeats while first <= last. Three moves are possible inside the loop.

When the loop ends because first > last, the search area is empty and the answer is "Search unsuccessful". The list itself never changes. Only the three index markers move.

The floor division // matters. For 15 elements, mid = (0 + 14) // 2 = 7. For an even count such as 10 elements, mid = (0 + 9) // 2 = 4, the left one of the two middle elements, so the two halves hold 4 and 5 elements.

Worked example: binary search, key found. Let numList = [2, 3, 5, 7, 10, 11, 12, 17, 19, 23, 29, 31, 37, 41, 43] (15 elements, indexes 0 to 14) and search for 23.

Three iterations were enough, whereas linear search would have needed 10 comparisons for this key. If the key is exactly the middle element (17 here), binary search finishes in 1 iteration, its best case.

Worked example: the worst case. Search the same list for 2, the very first element.

The number of elements still in play went 15, 7, 3, 1: halved each time. That is 4 iterations, the maximum for this list.

Worked example: key not present. Search the same list for 9.

Now first = 4 and last = 3, so first <= last is false and the loop ends: the search is unsuccessful after 4 iterations. A common wrong step is to stop at the third row because "9 lies between 7 and 11". The algorithm cannot know that until the search area is empty.

Program: binary search as a function. This version returns the index mid, or -1 when the key is absent, so the caller adds 1 to print a position.

Notice the two return conventions. Linear search returns index + 1 (a position) and None for failure. Binary search returns the raw mid (an index) and -1 for failure. Questions on this are really questions on reading the return statement.

Why it is so fast. After each iteration the area is halved, so the number of iterations in the worst case is $\lfloor \log_2 n \rfloor + 1$.

If the person you want sits at the exact middle of a sorted database of $2^{30}$ records, binary search finds them in 1 iteration, while linear search must compare about 537 million records first. That gap is why binary search ideas sit inside databases, routing tables in routers and compression codes, and why a dictionary or telephone directory is searched this way.

Beyond the textbook. For the exam: binary search needs a sorted list, and the sorting happens before the search. In reality: sorting a list costs more than one linear search over it, so binary search pays off when you search the same data many times, such as a contact book or a database index. For a single search in an unsorted list, plain linear search is the cheaper choice.

Pause and predict: A list of 10 sorted numbers is [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]. How many iterations does binary search need for the key 23, and what does the code return?

Check your answer: 3 iterations, returns index 5. First mid = (0 + 9) // 2 = 4 holds 16, and 23 > 16 so first = 5. Next mid = (5 + 9) // 2 = 7 holds 56, and 23 < 56 so last = 6. Then mid = (5 + 6) // 2 = 5 holds 23, a match. The function returns the index 5, and the printed position is 6.

Search by hashing: calculate, don't search

If you already knew which position a key must sit at, one comparison would settle the question. Hashing makes that possible. A hash function takes an element and produces an index; the elements are stored in a hash table at those indexes. To search, you apply the same function to the key, look at that one slot, and compare.

The simplest hash function is the remainder method, and it only works on numbers.

$$h(\text{element}) = \text{element} \bmod \text{size of the hash table}$$

In Python this is element % size. The remainder is the hash value, which is also the index in the table. Each slot of the table can hold only one item, and the table may be larger than the list.

Worked example: building a hash table. Store the list [34, 16, 2, 93, 80, 77, 51] in a hash table of 10 positions using h(element) = element % 10.

Placing each element at its index gives the table:

To search for 16, compute 16 % 10 = 6, look at index 6, and find 16: present, with a single comparison. To search for 46, compute 46 % 10 = 6, find 16 there, and 16 is not 46: absent, again with a single comparison. The time is the same whether the list has seven items or seven million, because the cost is one calculation plus one comparison.

Program: building a hash table and searching it.

The function returns (key % 10) + 1, the position, so 16 at index 6 is reported as position 7.

Collision. Hashing works perfectly only when every element maps to its own slot. Take the list [34, 16, 2, 26, 80] with h(element) = element % 10. Both 16 and 26 give the hash value 6, and one slot cannot hold two items. This clash is called a collision. Finding another slot for the element that lost the clash is called collision resolution. Several methods exist, but they are beyond this chapter, so the exam only asks you to recognise a collision and to know the term.

A hash function that maps every element of the list to a unique index is a perfect hash function, and with a perfect hash function collisions never occur. Real lists rarely allow that, so a perfect hash function is the ideal and collision resolution is the everyday reality.

Worked example: a bad table size. Use h(element) = element % 11 for [44, 121, 55, 33, 110, 77, 22, 66]. Every number is a multiple of 11, so every remainder is 0.

All eight elements fight for index 0, so seven collisions occur. The lesson is that the speed of hashing depends on how well the function spreads the data. A function that is cheap to compute but sends everything to one slot defeats the purpose.

Other hash functions exist apart from the remainder method: integer division, shift folding, boundary folding, mid-square, extraction and radix transformation. You only need to know their names. The time to compute a hash value does not depend on the number of items in the list, but it must be small enough that hashing still beats the other methods.

Beyond the textbook. For the exam: hashing is "one comparison", provided there is no collision. In reality: the dictionary and the set that you use in Python are built on hash tables, which is why checking key in my_dict stays fast even for huge dictionaries. They handle collisions behind the scenes, so the programmer never sees them.

Choosing the right search

Exam traps

60-second revision

Where this chapter connects

• Previous: Sorting arranges a list in order, which is exactly the condition binary search needs.
• Next: Understanding Data moves from searching a list to collecting, storing and summarising data.
• Same ideas elsewhere: Stack and Queue are other list based data structures built on the same Python list operations.