Algorithms · Lecture Notes
Chapter 4: Searching Algorithms
Finding a requested value in a collection is one of the things computers do most often. A name is looked up in a phone book, a student number in a database, a variable name in a compiler's symbol table. The question is always the same: is this value in the collection, and if so, where? These notes present seven methods that answer it. We begin with linear search and its sentinel variant, which need no preconditions. Next comes binary search, which halves the range at every step of a sorted array. A hash table, instead of comparing its way to a location, computes it. Interpolation, jump and exponential search exploit different properties of a sorted array. Each method comes with code, a step-by-step trace and a cost analysis, and the notes close by comparing the methods on the same array and choosing the right one.
Learning outcomes
- Basic searches
- Write linear search and binary search (the latter both iteratively and recursively) in Java, trace them step by step on an array, and work out their best, average and worst cases.
- Searching with hashing
- Explain hash functions, buckets, collisions, linear probing and chaining; interpret how the load factor affects cost.
- Advanced searches on a sorted array
- Justify the idea, the code and the complexities of interpolation, jump and exponential search: O(log log n), O(√n) and O(log i).
- Choosing a method
- Pick a suitable search algorithm according to whether the data is sorted, how it is distributed and how large it is; avoid common implementation mistakes.
4.1The search problem
Searching is one of the oldest and most widespread problems in computer science. A login screen that checks a user name, a point-of-sale program that looks up a product price and a text editor that runs a spell checker all do the same basic job. How fast that job is done can determine the performance of the whole program. If a search runs millions of times inside a loop, the few microseconds saved on each search add up to hours.
4.1.1Problem definition
Search algorithms are used to find a requested value in a collection of data. The algorithm scans the data according to a search criterion and tries to find an item that satisfies it. The criterion is usually a key. In student records the key is the student number, in a dictionary it is the word itself, in a phone book it is the person's name. In these notes we treat the problem in its simplest form: the items are in an array of integers and the key is the item's own value. In real applications each cell of the array holds a record and the comparison is made on the record's key field; the logic of the algorithms does not change.
Search problem: The input is an array arr of n items and a value key. The output is an index i such that arr[i] == key. If there is no such index, the output is −1; this outcome is called an unsuccessful search.
Two details of the definition matter. First, the output is not the value itself but its position. The sought value is already known; the real question is where it sits in the array. Once the position is known, the other fields of the record in that cell can be reached too. Second, an unsuccessful search is also a valid outcome. Since Java array indices start at 0, −1 cannot be confused with any valid index and safely carries the meaning "not found".
If the sought value occurs several times in the array, the definition accepts the index of any one of them. Which match is returned depends on the algorithm. Linear search scans from the front, so it finds the first match; binary search starts in the middle, so it may return a match that looks arbitrary. If the first or last match is specifically required, the algorithm has to be adapted accordingly.
4.1.2The cost measure: probes
Measuring how fast a search algorithm is in seconds is misleading, because the time depends on the processor, the language and the compiler. Instead, we count an operation that reflects the nature of the algorithm. In search algorithms the operation that determines the running time is comparing the key with an item of the array.
Looking at an array cell and comparing it with the key is called a probe. The cost of a search is measured by the number of probes it makes. All complexities in these notes describe how this number grows with n.
The reason for choosing the probe count is simple. The other work, such as incrementing loop counters and updating bounds, accompanies each probe in constant amount. The total time is therefore a constant times the probe count, and the order of growth is the same. In a hash table a probe means looking at a bucket and comparing the key stored there with the sought key; the definition fits that case as well.
Even for the same n, the cost varies from input to input. If the key is at the beginning of the array, linear search ends immediately; if it is at the end, the search walks the whole array. For this reason three cases are examined separately for each algorithm. The best case is the input that needs the fewest probes. The worst case is the input that needs the most probes, and it shows a guarantee the algorithm can give. The average case is the expected number of probes, computed under the assumption that the inputs follow a particular probability distribution. The worst case is often the most important measure, because it lets us say "no input will be slower than this".
4.1.3Kinds of search algorithms
Different search algorithms work on different principles and require different properties of the data as preconditions. The more preconditions an algorithm demands, the faster it tends to run once they are met. Table 4.1 summarizes the six methods studied in these notes with their preconditions and principles.
| Algorithm | Precondition | Operating principle |
|---|---|---|
| Linear search | none | Compares the items one by one. |
| Binary search | sorted array | Halves the collection to narrow the search range. |
| Hash search | hash table | The items are placed in a hash table; the search takes place in the key's bucket. |
| Interpolation search | sorted, uniformly distributed | Estimates the position from the ratio of the values. |
| Jump search | sorted array | Jumps over blocks of size √n, then searches linearly inside a block. |
| Exponential search | sorted array | Grows the bound 1, 2, 4, 8, …, then runs binary search. |
The preconditions in the table fall into three groups. Linear search asks for nothing; the array may be unsorted, or even a linked list. Hash search requires the data to be placed beforehand in a special structure, a hash table. The remaining four methods require a sorted array. What a sorted array tells us is this: if the value in a cell is smaller than the key, the key cannot be to the left of that cell. This single comparison eliminates a large part of the array at once. Binary, interpolation, jump and exponential search use this information in different ways.
The sortedness precondition has a price. Sorting an array takes O(n log n) time with the best comparison-based algorithms. For a single search, sorting the array first is more expensive than simply running linear search. Sorting pays for itself (it is amortized) only if many searches will be made on the same array.
4.2Linear search
Linear search is the first and simplest method that comes to mind. Because it requires nothing, it can be used in every situation. This generality is paid for with speed.
4.2.1The idea
Linear search checks every item in the list in order. Going through the products on a shopping list one by one, or combing a room corner by corner for a lost object, rests on the same idea. Starting at the beginning of the list, the key is compared with each item. If a match is found, the index of that item is returned. If the list ends without a match, the result is −1.
i = 2 is being compared.Sometimes the best way to find the information you want is really to look item by item. If the array is unsorted, there is no other choice. In an unsorted array, looking at one cell tells nothing about the others. Learning that 33 is not the key says nothing about whether 21 is. For an unsuccessful search to be able to answer "not present", therefore, it is necessary to look at every cell at least once. This simple observation shows that on unsorted data no algorithm can make fewer than n probes in the worst case.
4.2.2Code: linearSearch()
The Java code for linear search is as follows:
int linearSearch(int[] arr, int n,
int key) {
int i = 0;
while (i < n && arr[i] != key)
i++;
if (i < n)
return i; // found: index
else
return -1; // not found
}The method takes three parameters: arr holds the items to be searched, n the used size of the array, and key the value to look for. The return value is the index of the sought item, or −1 if it is not found. Passing the size as a separate parameter also covers the case where only the first n cells of the array are filled.
The line int i = 0; starts at the beginning of the array. The condition of the while loop has two parts: i < n checks that the end of the array has not been reached, and arr[i] != key checks that the key is not in that cell. As long as both are true, the loop body runs and i increases by one. The loop stops for one of two reasons: either i has reached n, or arr[i] equals the key. The if after the loop tells these two cases apart. If i < n is true, the loop stopped because of a match and i is the index of the match. If it is false, the array has been scanned from start to end without a match, and the method returns −1.
The order of the conditions matters. Java's && operator short-circuits: if the left side is false, the right side is never evaluated. When i == n, i < n is false and arr[n] is never accessed. Had the conditions been reversed, that is, arr[i] != key && i < n, the last step of an unsuccessful search would try to read arr[n] and throw an ArrayIndexOutOfBoundsException.
Writing the check after the loop as if (arr[i] == key). In an unsuccessful search the loop ends with i = n, and this check reads outside the array. The safe way to find out why the loop stopped is to test the bound (i < n) first.
4.2.3Best and worst case
The behavior of the algorithm can be seen on an unsorted example array of ten items:
arr = {33, 21, 12, 7, 8, 1, 3, 44, 56, 18}, n = 10
Best case: searching for 33. With i = 0, arr[0] = 33 equals the key. The second part of the loop condition is false on the first test, so the loop body never runs. Since i = 0 < n, the method returns 0. Only 1 comparison was made.
Worst case: searching for 17. 17 is not in the array. The algorithm can find that out only by looking at every item:
i = 0:arr[0] = 33 ≠ 17→i = 1.i = 1:arr[1] = 21 ≠ 17→i = 2.i = 2:arr[2] = 12 ≠ 17→i = 3.i = 3:arr[3] = 7 ≠ 17→i = 4.i = 4:arr[4] = 8 ≠ 17→i = 5.i = 5:arr[5] = 1 ≠ 17→i = 6.i = 6:arr[6] = 3 ≠ 17→i = 7.i = 7:arr[7] = 44 ≠ 17→i = 8.i = 8:arr[8] = 56 ≠ 17→i = 9.i = 9:arr[9] = 18 ≠ 17→i = 10.i = 10 = n:i < nis false and the loop ends. Theifcheck is false too, and the method returns −1.
The value comparison was made n = 10 times. The worst case is O(n).
The worst case arises with two different inputs: the key is absent, or it is found only in the last cell. In both, n value comparisons are made. The only difference is the final test of the loop. If the key is in the last cell, the loop stops at i = n − 1 with a match. If it is absent, the loop goes around once more and stops at i = n through the bound condition.
4.2.4Code trace: an average search
The best and worst cases are the two extremes. For a typical search, we look for 1 in the same array. The 1 sits near the middle of the array, at index 5. Table 4.2 shows every evaluation of the loop condition in the call linearSearch(arr, 10, 1).
| Test | i | i < n | arr[i] | arr[i] != 1 | Result |
|---|---|---|---|---|---|
| 1 | 0 | true | 33 | true | i++ |
| 2 | 1 | true | 21 | true | i++ |
| 3 | 2 | true | 12 | true | i++ |
| 4 | 3 | true | 7 | true | i++ |
| 5 | 4 | true | 8 | true | i++ |
| 6 | 5 | true | 1 | false | exit the loop |
On the sixth test arr[5] = 1 equals the key; the while condition becomes false and the loop is left. Then i = 5 < n is true and the method returns 5. In total 6 value comparisons were made. The general rule is clear: an item at index k is found with k + 1 comparisons.
4.2.5Complexity and evaluation
The cost of the best and worst cases is easy to read off: one is 1 comparison, the other n. The average case needs an assumption. The most common one is that the search is successful and that the key is equally likely to be at each position.
If the key is in the array and is equally likely, with probability 1/n, to be at each of the n positions, then the average number of comparisons in linear search is (n + 1)/2.
The item at position i (counting from 1) is found with i comparisons. The expected value is the sum of each position's cost times its probability: Σi=1n i · (1/n) = (1/n) · n(n + 1)/2 = (n + 1)/2. Here we used the identity 1 + 2 + … + n = n(n + 1)/2. □
For n = 10 the average is 11/2 = 5.5 comparisons. The result agrees with intuition: on average the key is in the middle of the array, so about half of it is examined. In an unsuccessful search, n comparisons are always made. Table 4.3 puts the three cases together.
| Case | Comparisons | Order | Example (n = 10) |
|---|---|---|---|
| Best (first item) | 1 | O(1) | 33 → 1 comparison |
| Average (successful, equally likely) | (n + 1)/2 | O(n) | 5.5 on average |
| Worst / unsuccessful | n | O(n) | 17 → 10 comparisons |
It is an important result that the average case is also O(n). The average cost is only half of the worst case, and halving does not change the order. If the array grows tenfold, the average search takes ten times as long. As for extra memory, the situation is good: the algorithm uses only the variable i, so the extra memory is O(1).
The advantages of linear search can be listed as follows:
- It is easy to code and to understand; it needs no complicated data structure.
- It needs no preparation: the array does not have to be sorted.
- It is ideal for small collections. To look up a number in a personal contact list, no more complicated method is needed.
- It also works on structures that can only be accessed sequentially, such as a linked list. Binary search cannot work efficiently on a linked list, because even reaching the middle item takes O(n) steps.
Its disadvantages are equally clear:
- It is slow on large data. In an array of 106 items a successful search makes 500,000 comparisons on average.
- Even if the array is sorted, it does not use that information. In a sorted array the search could stop on meeting a value larger than the key; the basic algorithm does not do this.
- If many queries will be made on the same array, sorting it once and using binary search is much cheaper.
4.2.6Sentinel linear search
Looking carefully at the loop of linear search, we see that two comparisons are made on every iteration: i < n and arr[i] != key. Only the second is the real work of the search. The first is a safety check put there so that we do not run off the end of the array. There is a clever way to remove this check from the loop.
A sentinel is a special value placed at the end of the array to guarantee that the loop stops. In sentinel linear search the key itself is written into the last cell. The loop then finds a match at the last cell at the latest, and the i < n test is no longer needed.
The code looks like this:
int sentinelSearch(int[] arr, int n,
int key) {
if (n == 0) return -1;
int last = arr[n - 1];
arr[n - 1] = key; // sentinel
int i = 0;
while (arr[i] != key)
i++;
arr[n - 1] = last; // restore
if (i < n - 1 || last == key)
return i;
return -1;
}The method first saves the last item in the variable last and writes the key into the last cell. From this point on the array holds at least one copy of the key. The loop now tests only arr[i] != key; i cannot exceed the bound, because a match is found at position n − 1 at the latest. When the loop ends, the old value is written back into the last cell, and the array returns to its original state.
The last step needs care. The place where the loop stops can mean two things. If i < n − 1, the match was found before the sentinel, in a real item. If i == n − 1, the loop stopped at the sentinel. Even then the key may have been found: if the array's real last item equals the key. That is why the second part of the if condition is last == key. If either condition holds, i is returned; if both are false, −1.
The gain in numbers is as follows. In an unsuccessful search the classic loop makes n value comparisons and n + 1 bound tests, about 2n comparisons in all. The sentinel loop makes n value comparisons. Two more comparisons come after the loop: i < n − 1 and last == key. The total is about n + 2. The number of comparisons almost halves, but the order is still O(n). This is an improvement that shrinks the constant factor.
Using sentinel search on a read-only array, or on an array that other threads are reading at the same time. During the search the last cell is temporarily changed. If another thread reads the array in the meantime, it sees a wrong value. Forgetting to write the last item back also corrupts the array permanently.
4.2.7Code trace: sentinelSearch()
A trace of sentinel search on an unsuccessful search: arr = [7, 3, 9, 4, 6], n = 5, key 5. The 5 is not in the array.
- Setup. The last item, 6, is saved in
last. The key 5 is written into the last cell as the sentinel; the array temporarily becomes[7, 3, 9, 4, 5].i = 0. arr[0] = 7 ≠ 5→i = 1. There is only one comparison in this iteration; thei < ntest is not made.arr[1] = 3 ≠ 5→i = 2.arr[2] = 9 ≠ 5→i = 3.arr[3] = 4 ≠ 5→i = 4.arr[4] = 5equals the key, and the loop stops. But what was found is not a real item; it is the sentinel.- The last item is put back: the array is again
[7, 3, 9, 4, 6]. - The test
i < n − 1is 4 < 4, which is false. The testlast == keyis 6 ≠ 5, which is also false. The method returns −1.
Total number of comparisons: 5 in the loop and 2 at the end, that is 7 = n + 2. The classic loop would have made 5 value comparisons and 6 bound tests on the same search; counted as about 2n, that is 10.
last. (b) The loop stopped at the sentinel and 6 has been put back; since both final tests are false, the result is −1 and 7 comparisons were made in total.A different example shows why the second if condition is needed: arr = [12, 5, 9, 20, 7] and key 7. Here the key really is in the last cell. 7 is written as the sentinel anyway, and the loop stops at i = 4. i < n − 1 is false, but last == key is true, and the method correctly returns 4. Without this condition, the real last item of the array could never be found.
4.3Binary search
Linear search eliminates only one cell of the array per probe. If the array is sorted, a single probe can say much more. If the middle item is smaller than the key, then by sortedness every item to its left is also smaller than the key, and none of them can be the key. A single probe eliminates half the array. Binary search is built on this observation.
4.3.1The idea
Looking for a book in a library is a good analogy. The books are arranged alphabetically by the author's surname. Instead of walking along all the shelves from the start, you first go to the middle section. If the book you want falls to the left of the middle shelf, you continue on the shelves to the left; if to the right, on the shelves to the right. In the remaining section you again go to the middle. Every comparison halves the part that has to be searched.
Binary search compares the item in the middle of the search range of a sorted array with the key. If the values are equal, the search ends. If the key is smaller, the search continues in the left half of the range; if larger, in the right half. If the range becomes empty, the key is not in the array.
Binary search has two preconditions. First, the array must be sorted; throughout these notes, sorted means sorted in increasing order. Second, items must be accessible by index in O(1) time. This second condition holds for an array but not for a linked list. In a linked list, reaching the middle item means walking half the list from the front. In that case even a single "middle" computation is as expensive as linear search.
lo = 5 and hi = 8.4.3.2Why is binary search fast?
The power of binary search comes from the range halving at every step. In a list of 1000 items, linear search makes 500 checks on average. Binary search finishes in at most 10 steps. The range sizes shrink after each comparison as follows:
1000 → 500 → 250 → 125 → 62 → 31 → 15 → 7 → 3 → 1
There are ten range sizes in this sequence and each corresponds to one comparison: 10 comparisons in all. In halving, the fractional part is dropped, because once the middle item has been compared it is no longer in the range. For example, when the middle item is removed from a range of 125 items, 62 items remain on each side.
How effective this shrinking is shows up for large values of n. Table 4.4 puts the worst-case comparison counts of the two methods side by side.
| n | Linear (worst) | Binary (worst) |
|---|---|---|
| 10 | 10 | 4 |
| 1,000 | 1,000 | 10 |
| 106 | 106 | 20 |
| 109 | 109 | 30 |
Binary search makes at most ⌊log2 n⌋ + 1 comparisons. In an array of a billion items, 30 comparisons suffice. When the data grows 1000-fold, binary search gains only about 10 steps, since 210 = 1024 ≈ 1000. Linear search becomes 1000 times slower. This kind of growth is called logarithmic growth.
4.3.3Code: iterative binarySearch()
The Java code for binary search written with a loop (iteratively) is as follows:
int binarySearch(int[] arr, int n, int key) {
int lo = 0, hi = n - 1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (key < arr[mid])
hi = mid - 1; // left half
else if (key > arr[mid])
lo = mid + 1; // right half
else
return mid; // found
}
return -1;
}lo and hi are the lower and upper bounds of the range to be searched; both are inclusive. At the start the range is the whole array: lo = 0, hi = n − 1. The condition while (lo <= hi) keeps the loop going as long as the range is not empty. When lo == hi the range holds a single item, and that item must be tested as well; this is why the condition uses <=.
In each iteration, mid is computed as the index of the item in the middle of the range. Because integer division drops the fractional part, if the range has an even number of items the left one of the two middle items is chosen. Then there are three paths. If the key is smaller than arr[mid], the key, if present, is to the left of the middle; hi = mid − 1 moves to the left half. If the key is larger, lo = mid + 1 moves to the right half. If they are equal, mid is returned. If the loop ends without finding a match, the range has become empty (lo > hi) and the method returns −1.
Updating the bounds with mid − 1 and mid + 1 is critical. The middle item has just been tested and found not to be the key, so it is not taken into the new range. This rule also guarantees that the range shrinks by at least one item in each iteration, and hence that the loop always terminates.
4.3.4The recursive version
Binary search is naturally recursive: searching in one half of the range is a smaller instance of the same problem. The recursive Java code is as follows:
int search(int[] arr, int lo,
int hi, int key) {
if (lo > hi) return -1; // empty range
int mid = (lo + hi) / 2;
if (arr[mid] == key) return mid;
if (arr[mid] < key) // right half
return search(arr, mid + 1, hi, key);
return search(arr, lo, mid - 1, key);
}The first call is search(arr, 0, n - 1, key). The method first checks the base case: if lo > hi, the range is empty and it returns −1. Otherwise the middle item is computed, and if it equals the key its index is returned. If not, the same method is called again on the right half if the key is larger, or on the left half if it is smaller, and its result is returned as is. The parameters of the new call take the place of the lo and hi updates of the iterative version.
From the point of view of algorithm design, binary search is the simplest example of the divide-and-conquer approach. The divide step is choosing the middle item. The conquer step is to continue in one half only; the other half is never touched. There is no combine step, because the answer to the subproblem is directly the answer to the problem. Since there is only one branch, this approach is also called decrease and conquer. The cost is described by the following recurrence:
T(n) = T(n/2) + 1
The recurrence says that a search on n items makes one comparison and then a search on n/2 items. Its solution is T(n) = O(log n).
The two versions make the same comparisons, but their memory use differs. The iterative version uses only a few variables: the extra memory is O(1). In the recursive version each call opens a frame on the call stack, and the calls nest at most ⌊log2 n⌋ + 1 deep. The extra memory is O(log n). This is small; even for a billion items 30 frames suffice. Still, the iterative version is lighter both in memory and in call cost, and is more often preferred in practice.
4.3.5Binary search and the balanced binary search tree
The comparisons made by binary search can be drawn as a tree. This drawing lets us see why the algorithm takes at most ⌊log2 n⌋ + 1 steps. As an example, take a sorted array of 15 items:
5, 11, 12, 14, 15, 18, 19, 21, 23, 25, 27, 28, 30, 32, 37
- Root. The middle of the whole array is 21 at index 7. The first comparison of binary search is always with 21; 21 is the root of the tree.
- Second level. If the key is smaller than 21, the search continues among indices 0–6; the middle of this range is 14 at index 3. If larger, it continues in the range 8–14; the middle is 28 at index 11. 14 becomes the left child of the root and 28 the right child.
- Third level. The middle of each subrange forms the next level: 11 from the range 0–2, 18 from 4–6, 25 from 8–10, 32 from 12–14.
- Leaves. The remaining eight items (5, 12, 15, 19, 23, 27, 30, 37) are one-item ranges and become leaves.
The tree has 4 levels and height 3. Since ⌊log2 15⌋ + 1 = 3 + 1 = 4, every search makes at most 4 comparisons. For successful searches the average number of comparisons is (1 · 1 + 2 · 2 + 4 · 3 + 8 · 4)/15 = 49/15 ≈ 3.27.
This tree is a binary search tree: the values in the left subtree of every node are smaller than the node, and those in the right subtree are larger. Moreover, it is the most balanced tree possible; every level is completely full. Binary search on a sorted array is the same thing as walking down from the root of this best tree. The cost of a search in a tree is found by adding one to the depth of the node sought. The worst case depends on the height of the tree. The height of a balanced tree with n nodes is ⌊log2 n⌋. Had the tree been built unbalanced, for example with every node having only a right child, the height would be n − 1 and the search would degrade to linear search.
4.3.6Searching the implicit tree
The tree does not have to be built in memory. The sorted array is the tree itself; the mid computation walks the tree implicitly. The left child of a node is the middle of the left half range, and its right child is the middle of the right half. A second sorted array shows this. The array again has 15 items:
1, 3, 5, 6, 7, 8, 11, 14, 16, 18, 20, 22, 23, 25, 27
Searching for 20.
lo = 0,hi = 14→mid = 7,arr[7] = 14. Since 20 > 14, we go right:lo = 8.mid = (8 + 14)/2 = 11,arr[11] = 22. Since 20 < 22, we go left:hi = 10.mid = (8 + 10)/2 = 9,arr[9] = 18. Since 20 > 18, we go right:lo = 10.mid = (10 + 10)/2 = 10,arr[10] = 20: found, 10 is returned.
From root to leaf, 4 comparisons were made. The path in the tree is 14 → 22 → 18 → 20.
The tree view also explains an unsuccessful search. If the key is not in the array, the search descends to a leaf and tries to go to an empty child of that leaf. This empty child corresponds to the gap into which the key would be inserted without breaking the order. For example, if 19 is searched for in this array, the path is 14 → 22 → 18 → 20. Since 19 is smaller than 20, the search wants to go to the left child of 20, but that child is empty. 19 would have fit between 18 and 20.
4.3.7Best and worst case
The two extremes of the code can be counted on an array of nine items:
arr = {5, 7, 10, 17, 23, 34, 55, 67, 99}, n = 9
Best case: searching for 23. lo = 0, hi = 8; mid = (0 + 8)/2 = 4 and arr[4] = 23 equals the key. It is found in one step and 4 is returned. The best case is O(1); the key is exactly in the middle.
Worst case: searching for 54. 54 is not in the array.
mid = 4: 23 < 54 →lo = 5. The left half (0–4) is eliminated.mid = (5 + 8)/2 = 6: 55 > 54 →hi = 5.mid = (5 + 5)/2 = 5: 34 < 54 →lo = 6.lo = 6 > hi = 5: the range is empty, the loop ends and −1 is returned.
The search was found to be unsuccessful in 3 comparisons. If 54 were in the array, it would sit between 34 and 55, at index 6. When the loop ends, lo shows exactly this insertion position.
lo = 6 and hi = 5; the range is empty and all cells have been eliminated.In this array the worst case is actually 4 comparisons: ⌊log2 9⌋ + 1 = 4. The search for 54 ending in 3 steps is because the key fails on a shallow branch of the tree. For example, if 99 is searched for, the probed indices are 4, 6, 7, 8 and 4 comparisons are made. The bound gives the worst case; not every unsuccessful search reaches it.
4.3.8Code trace: binarySearch(arr, 9, 47)
A trace of a successful search with variable values is below. The array is {0, 4, 7, 10, 14, 23, 45, 47, 53} and the key is 47.
| Iteration | lo | hi | mid | arr[mid] | Comparison | Action |
|---|---|---|---|---|---|---|
| 1 | 0 | 8 | 4 | 14 | 47 > 14 | lo = 5 |
| 2 | 5 | 8 | 6 | 45 | 47 > 45 | lo = 7 |
| 3 | 7 | 8 | 7 | 47 | 47 = 47 | return 7 |
In the first iteration lo ≤ hi is true; the middle is computed as (0 + 8)/2 = 4 and arr[4] = 14. Since 47 is larger, the left part is eliminated: lo = 5. In the second iteration the middle is (5 + 8)/2 = 6, and arr[6] = 45 is again smaller: lo = 7. In the third iteration the middle is (7 + 8)/2 = 7 and arr[7] = 47 equals the key; the method returns 7. In nine items, 3 comparisons were made. For this array the bound is ⌊log2 9⌋ + 1 = 4.
lo = mid = 7, hi = 8. 47 has been found (green); the cells eliminated in the first two iterations are gray.There is a detail in counting comparisons. Each iteration of the code contains two written comparisons: key < arr[mid] and, if needed, key > arr[mid]. But both look at the same cell; the probe count goes up by one. In these notes, looking at one middle item is counted as one comparison. In Java, for integers, a single Integer.compare call can also be used instead of two comparisons.
4.3.9Complexity
The worst case of binary search is stated exactly as follows.
On a sorted array of n ≥ 1 items, binary search runs for at most ⌊log2 n⌋ + 1 iterations. Hence the worst-case cost is O(log n).
Let the range hold s items at the start of an iteration. After the middle item is removed, ⌊(s − 1)/2⌋ items remain on the left and ⌈(s − 1)/2⌉ = ⌊s/2⌋ on the right. Whichever half is taken, the new range has at most ⌊s/2⌋ items. Since s = n at the start, after k iterations the range holds at most ⌊n/2k⌋ items. For an iteration to be made, the range must not be empty. For iteration k + 1 to be made, we need n/2k ≥ 1, that is, k ≤ log2 n. Hence the iteration number can be at most ⌊log2 n⌋ + 1. □
The theorem also agrees with the solution of the recurrence T(n) = T(n/2) + 1. Unrolling the recurrence gives T(n) = T(n/2k) + k. When n/2k = 1, that is for k = log2 n, the subproblem has constant cost. The total is of order log2 n.
| Case | Order |
|---|---|
| Best (first middle matches) | O(1) |
| Average | O(log n) |
| Worst / unsuccessful | O(log n) |
| Extra memory | iterative O(1), recursive O(log n) |
| Preparation (sorting) | O(n log n), once |
That the average case is also O(log n) is clear from the tree view. In a balanced tree about half of the nodes are leaves, and the leaves are at the greatest depth. A randomly chosen item is most likely on the lower levels. In the example with 15 items the average was 3.27 and the worst case 4 comparisons; the difference between the two is constant.
The last row of the table is the hidden price of binary search. If the array is unsorted, it must first be sorted, and that takes O(n log n). Sorting is done once, searches many times. For k queries the costs of the two routes are as follows:
- Linear search: O(k · n) in total.
- Sort once, then binary search: O(n log n + k log n) in total.
If k is small, for example a single query, linear search is cheaper. Once k exceeds the order of log n, the cost of sorting pays for itself, and the gap widens quickly as k grows.
On an unsorted array of n = 106 items, k = 1000 searches will be made. Linear search needs 1000 · 106 = 109 comparisons in the worst case. Sorting first takes about n log2 n ≈ 106 · 20 = 2 · 107 comparisons. Then 1000 binary searches make at most 1000 · 20 = 2 · 104 comparisons. The total is about 2 · 107, roughly 50 times fewer than the linear route.
4.3.10Implementation details
Binary search is simple as an idea, but surprisingly hard to write correctly. Knuth reports that the first binary search was published in 1946, but a bug-free version appeared only in 1962. Most of the bugs cluster around four details.
Overflow in the midpoint. The expression (lo + hi) / 2 is correct mathematically, but in Java an int holds at most 231 − 1 = 2,147,483,647. If lo + hi exceeds this limit, the sum wraps around to a negative number and mid becomes negative. For the sum of two indices to exceed this limit the array must have more than about a billion (230) items. This limit once looked far away; today it is a real risk for large arrays and file offsets. In the Java library's Arrays.binarySearch this bug went unnoticed for years and was fixed in 2006. Safe ways to write it are:
lo + (hi - lo) / 2 or (lo + hi) >>> 1
The first divides the difference and never overflows. The second turns the overflowed sum back into the correct value with an unsigned right shift. For example, for lo = 2,000,000,000 and hi = 2,100,000,000, the expression (lo + hi) / 2 gives −97,483,648; both safe forms give the correct result, 2,050,000,000.
Updating the bounds. Writing hi = mid or lo = mid may fail to shrink the range. When lo == hi and the key is smaller than arr[mid], the assignment hi = mid leaves the range unchanged and the loop runs forever. Since the middle item has already been checked, the bounds must be updated by ±1.
Duplicate items. Returning immediately on equality gives any one of the matches. If 4 is searched for in the array {2, 4, 4, 4, 4, 7, 9, 12}, iterative binary search looks at index 3 in the first iteration and returns 3, although the first 4 is at index 1. If the first position is wanted, the result is recorded on equality and the search continues to the left with hi = mid − 1.
The Java library. Arrays.binarySearch(arr, x) runs binary search on a sorted array. If the value is found it returns its index; with duplicate items it is unspecified which one is returned. If it is not found, it returns −(insertion point) − 1. The insertion point is the index at which x would be inserted without breaking the order. The return value is always negative to signal "not found", and its absolute value carries the position. For example, if 5 is searched for in {2, 4, 4, 4, 4, 7, 9, 12}, the insertion point is 5 and the method returns −5 − 1 = −6. Had it returned only "−(insertion point)", a value whose insertion point is 0 would return 0 and be confused with a found item.
Writing the loop condition as while (lo < hi). This condition skips a single-item range: if the key is in the last remaining cell, the loop is left without testing it and −1 is returned. If 10 is searched for in {5, 7, 10}, then in the first iteration lo = 2, hi = 2 and the loop ends without ever looking at 10.
4.3.11First occurrence among duplicates
Binary search that finds the first position of the key in a sorted array containing duplicates is written as follows:
int firstIndex(int[] arr, int key) {
int lo = 0, hi = arr.length - 1, result = -1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (arr[mid] == key) {
result = mid; // record,
hi = mid - 1; // look left
} else if (arr[mid] < key)
lo = mid + 1;
else
hi = mid - 1;
}
return result;
}The code departs from iterative binary search in two places. First, the variable result holds the leftmost match found so far; its initial value is −1. Second, on equality the method does not return. It records the index of the match in result and, with hi = mid − 1, checks whether there was an earlier match to the left. The loop runs until the range is empty, and finally result is returned. The midpoint is also written in the overflow-safe way.
| Iteration | lo | hi | mid | arr[mid] | Action | result |
|---|---|---|---|---|---|---|
| 1 | 0 | 7 | 0 + (7 − 0)/2 = 3 | 4 | equal: record, hi = 2 | 3 |
| 2 | 0 | 2 | 0 + (2 − 0)/2 = 1 | 4 | equal: record, hi = 0 | 1 |
| 3 | 0 | 0 | 0 | 2 | 2 < 4: lo = 1 | 1 |
| — | 1 | 0 | lo > hi: the loop ends | return 1 | ||
The array holds four 4s (indices 1–4). In the first iteration the 4 at index 3 is found, but it may not be the first 4. It is recorded and the search looks left. In the second iteration the 4 at index 1 is found; it is recorded too. In the third iteration the 2 at index 0 is smaller than the key and the range shifts right. When the range becomes empty, the last recorded value, 1, is returned. There were 3 probes, and the time is still O(log n).
firstIndex. lo = 1 > hi = 0 has been reached; result = 1 is the index of the first 4.The same idea is used to find the last position: on equality the result is recorded and the search continues to the right with lo = mid + 1. The difference between the two methods also gives the number of times the key occurs in the array. In the example the last position is 4 and the first is 1; the value 4 occurs 4 − 1 + 1 = 4 times. This count takes O(log n) however many repetitions there are.
Finding the first position by scanning linearly to the left after finding any match. The result is correct, but if all items are equal the scan takes n steps and the cost rises to O(n). Narrowing the search range on equality keeps the cost logarithmic in every case.
4.4Searching with hashing
The methods so far find the location of the key by comparing. Each comparison yields some information and reduces the candidate positions. Every comparison-based method has a lower bound: even in a sorted array, about log2 n comparisons cannot be avoided in the worst case. Hash search gets past this bound by another route. It does not search for the location; it computes it.
4.4.1The idea: compute the location
Hash search works on a principle like a key fitting exactly into its own lock. The data consist of keys and the values that go with them. The key is converted into a table index by a hash function. This index is called the key's hash value, and it shows where the data sit in the table.
A hash table is an array of m cells; each cell is called a bucket. A hash function h converts each key into a bucket number between 0 and m − 1. A key x is placed in bucket h(x) and searched for there.
The search takes place in the bucket that corresponds to the key's hash value. If the bucket is not empty, the key is compared with the keys in the bucket. If a match is found, the search ends. The cost of a search is made up of computing the hash value and a few comparisons in that bucket. This cost is independent of the number of keys in the table. That is why in a well-designed hash table the average search time is O(1).
In the examples of these notes the keys are integers and the hash function is h(x) = x % 10. This function takes the last digit of the key and makes it the bucket number. The function is simple, but enough to show the principle. In real applications the number of buckets is often chosen as a prime or a power of two, and the function uses all the bits of the key.
4.4.2Advantages and disadvantages
The advantages of hash search are as follows:
- It is very fast on average: O(1).
- The data do not have to be sorted beforehand.
- It is ideal for large collections and for applications that mix many insertions and searches. Inserting a new item into a sorted array requires shifting items; in a hash table insertion is also O(1) on average.
- If the hash function is well chosen, the sought item is reached directly.
It also has disadvantages:
- The hash function can lead to collisions.
- When a collision occurs, extra processing steps are needed. In the worst case all keys fall into the same bucket and the search degrades to O(n).
- It needs extra memory; part of the table is always kept empty.
- The table scatters keys without regard to order. For that reason, visiting the keys in sorted order, finding the smallest key, or answering range queries such as "keys between 50 and 100" is not efficient.
A collision is when two different keys fall on the same hash value: h(x) = h(y) while x ≠ y.
Collisions are unavoidable. The number of possible keys is far greater than the number of buckets; by the pigeonhole principle some keys must share a bucket. For example, if all integers are distributed over 10 buckets, every number with the same last digit falls in the same bucket. The design of a hash table therefore involves two questions: how do we choose a hash function that reduces collisions, and how do we resolve the unavoidable ones?
4.4.3The hash function
When the key is a string, it must first be converted into a number. The simplest way is to add up the numeric codes of the characters:
int hash(String key, int m) {
int sum = 0;
for (char c : key.toCharArray())
sum += c; // Unicode code
return sum % m; // m: table size
}The method walks over the characters of the key one by one. In Java the char type behaves like an integer; the line sum += c adds the character's Unicode code to the sum. When the loop ends, the sum is reduced to the range 0 to m − 1 by taking it modulo the table size m. The method runs in O(L) time, where L is the length of the key.
| Key | Character codes | Sum % 10 |
|---|---|---|
"ali" | 97 + 108 + 105 = 310 | 0 |
"ila" | 105 + 108 + 97 = 310 | 0 |
"veli" | 118 + 101 + 108 + 105 = 432 | 2 |
The function is simple but weak. Addition does not see order: words made of the same letters always give the same sum. That is why "ali" and "ila" collide in bucket 0. "kar" and "ark" collide for the same reason. Moreover, the sums of short words are bunched in a narrow range; in a large table most buckets would never be used.
A good hash function has two properties at once: it is computed quickly, and it spreads keys evenly over the buckets. Java's String.hashCode() gives each character a weight that depends on its position:
h(s) = Σi=0L−1 s[i] · 31L−1−i
In this sum the position of the character matters too. For "ali" the value is 97 · 312 + 108 · 31 + 105 = 96,670, and for "ila" it is 104,350; the two words are now told apart. Because the sum can be large, an int overflows, but this is not a problem: overflow keeps on mixing the values. The bucket number is found by taking this value modulo m after fixing its sign.
4.4.4Code trace: hash("veli", 10)
key = "veli", m = 10. At the start sum = 0.
c = 'v': its Unicode code 118 is added,sum = 118.c = 'e': 101 is added,sum = 219.c = 'l': 108 is added,sum = 327.c = 'i': 105 is added,sum = 432.- 432 % 10 = 2: "veli" falls into bucket 2.
The same computation gives 310 for "ali" and "ila"; both collide in bucket 0.
4.4.5Searching with linear probing
There are two main ways to resolve a collision. In the first, each key is placed in one of the table's own cells; if its bucket is full, another empty bucket is looked for. This approach is called open addressing. The simplest open-addressing method is linear probing.
Linear probing: If the key's bucket h(x) is full, the buckets h(x) + 1, h(x) + 2, … are examined in turn; on reaching the end of the table, the search wraps around to the start. Insertion goes into the first empty bucket. Search follows the same sequence and stops when it finds the key or reaches an empty bucket.
Search in a table that uses linear probing is written as follows:
int hashSearch(Integer[] table, int key) {
int m = table.length; // m > 0
int index = Math.floorMod(key, m); // hash
while (table[index] != null) {
if (table[index] == key)
return index; // found
index = (index + 1) % m; // next bucket
}
return -1; // empty: absent
}The table is of type Integer[], so an empty bucket can be represented by null. In this example the table stores only keys; in a general implementation each bucket holds a key-value pair. m is the table size. The first bucket to look at is Math.floorMod(key, m); key % m would give a negative index for a negative key. The table must not be empty (m > 0).
The while loop runs until table[index] is empty. In each iteration the key in the bucket is compared with the sought key. If they match, the bucket's index is returned; in a key-value table the value would be returned here. If there is no match, we move on to the next bucket. The expression (index + 1) % m wraps from the last bucket back to bucket 0; the table is scanned circularly. If an empty bucket is reached, the key is not in the table and the method returns −1.
The logic of stopping at an empty bucket comes from how insertion works. When a key is inserted, it is placed in the first empty bucket starting from its own bucket. So if the key is in the table, all the buckets from its own bucket up to its location are full. If an empty bucket is met during a search, the key cannot be further on.
Assuming that the comparison table[index] == key is safe with Integer objects. Here key is an int, so Java unboxes table[index] and compares the numbers, and the result is correct. If both sides were Integer, == would compare object identities; for values outside −128 to 127, even equal numbers could come out "not equal". When comparing two objects, equals must be used.
4.4.6Inserting with linear probing
Let the following keys be inserted in order into an empty table (m = 10): 16, 12, 45, 29, 6, 122, 5, 58, 75. The hash function is h(x) = x % 10.
| Key | h(x) | Buckets probed | Bucket used | Probes |
|---|---|---|---|---|
| 16 | 6 | 6 | 6 | 1 |
| 12 | 2 | 2 | 2 | 1 |
| 45 | 5 | 5 | 5 | 1 |
| 29 | 9 | 9 | 9 | 1 |
| 6 | 6 | 6 (full), 7 | 7 | 2 |
| 122 | 2 | 2 (full), 3 | 3 | 2 |
| 5 | 5 | 5, 6, 7 (full), 8 | 8 | 4 |
| 58 | 8 | 8, 9 (full), 0 | 0 | 3 |
| 75 | 5 | 5, 6, 7, 8, 9, 0 (full), 1 | 1 | 7 |
The first four keys go directly into their own buckets. The bucket of 6, bucket 6, holds 16, so 6 moves on to the next bucket, 7. 122 likewise slides from 2 to 3. The case of 5 is more interesting: buckets 5, 6 and 7 are full, and 5 can be placed only in 8. The bucket 8 of 58 has just been taken by 5; 58 finds 9 full as well and wraps from the end of the table to the start, settling in 0. The last key, 75, has bucket 5, and all buckets from 5 through 0 are full. After seven probes, 75 is placed in bucket 1.
In the final state the full buckets 5, 6, 7, 8, 9, 0, 1, 2, 3, in that order, have formed one contiguous cluster; only bucket 4 is empty. This phenomenon is called primary clustering. As a cluster grows, a new key that falls into any bucket of the cluster has to walk to the end of the cluster and makes the cluster one bucket larger. Large clusters tend to get larger. This is why linear probing slows down quickly as the table fills.
4.4.7Code trace: hashSearch(table, 75)
We search for 75 in the resulting table. The table is [58, 75, 12, 122, null, 45, 16, 6, 5, 29].
| Probe | index | table[index] | Comparison | Next index |
|---|---|---|---|---|
| 1 | 5 | 45 | 45 ≠ 75 | (5 + 1) % 10 = 6 |
| 2 | 6 | 16 | 16 ≠ 75 | 7 |
| 3 | 7 | 6 | 6 ≠ 75 | 8 |
| 4 | 8 | 5 | 5 ≠ 75 | 9 |
| 5 | 9 | 29 | 29 ≠ 75 | (9 + 1) % 10 = 0 |
| 6 | 0 | 58 | 58 ≠ 75 | 1 |
| 7 | 1 | 75 | 75 = 75 | return 1 |
The search starts at bucket 75 % 10 = 5. 45, 16, 6, 5 and 29 are passed in turn; after bucket 9 the search wraps from the end to the start. After 58 in bucket 0 is passed as well, 75 is found in bucket 1 and the method returns 1. As with insertion, the search took 7 probes: 75's location was reached at the end of the cluster.
hashSearch(table, 75), index = 1; 75 has been found.An unsuccessful search is more expensive. If 35 is searched for in the same table, the search again starts at 5 and continues until it reaches 4, the only empty bucket: buckets 5, 6, 7, 8, 9, 0, 1, 2, 3, 4 are examined. Nine key comparisons and one empty bucket make 10 probes. In this table the average over successful searches is 22/9 ≈ 2.44 probes; most keys sit close to their own bucket.
4.4.8Chaining
The second way to resolve collisions is to put more than one key in a bucket.
In separate chaining, each bucket holds the head of a linked list. Keys that fall into the same bucket are added to this list. Search walks the list in the key's bucket from start to end.
Let the same keys be inserted, with the same hash function, into a table that uses chaining. 16, 12, 45 and 29 fall into empty buckets and form one-item lists. When 6 is inserted, bucket 6 is full; this is a collision, but 6 does not slide to another bucket, it is appended to the end of 16's list. 122 is appended to the list of bucket 2 after 12. 5 goes behind 45 in the list of bucket 5. 58 settles in the empty bucket 8. Finally 75 is appended to the list of bucket 5 as the third item.
In chaining, to search for 75 only the list of bucket 5 is walked: 45 ≠ 75, 5 ≠ 75, 75 = 75. It is found in three comparisons. This is far fewer than the 7 probes of linear probing, because chaining has no clustering. Each key is compared only with keys that share its own hash value. 16, which falls into bucket 6, and 75, which falls into bucket 5, never meet.
Chaining has other advantages as well. The table never "fills up"; the lists can grow. Deletion is easy too: the item is removed from the list. In linear probing, by contrast, deleting a key and emptying its bucket cuts the path to the keys behind it; the deleted bucket has to be marked "deleted". The price of chaining is storing a separate object and a pointer for each node. That means both extra memory and scattered access in memory. Linear probing keeps keys in consecutive cells and so uses the cache better.
Searching for 35 in the chaining table. h(35) = 5; the list of bucket 5 is 45 → 5 → 75. 45 ≠ 35, 5 ≠ 35, 75 ≠ 35 and the list ends. After 3 key comparisons the search turns out to be unsuccessful. The same search in the linear-probing table had needed 9 key comparisons and one empty bucket, 10 probes in all.
4.4.9Load factor and complexity
The quantity that really determines the performance of a hash table is how full the table is.
The load factor is α = n / m, where n is the number of keys in the table and m is the number of buckets.
In chaining, α is the average length of a list and can exceed 1. In linear probing each bucket holds at most one key, so α ≤ 1. In our example tables 9 keys were put into 10 buckets: α = 0.9.
Under the uniform hashing assumption, in which keys are distributed over the buckets randomly and independently of one another, Knuth gives the following approximate formulas for the average number of probes:
| Method | Successful search | Unsuccessful search | α = 0.5 | α = 0.9 |
|---|---|---|---|---|
| Chaining | ≈ 1 + α/2 | ≈ 1 + α | 1.25 / 1.5 | 1.45 / 1.9 |
| Linear probing | ≈ ½ (1 + 1/(1 − α)) | ≈ ½ (1 + 1/(1 − α)2) | 1.5 / 2.5 | 5.5 / 50.5 |
The numbers in the table are computed directly from the formulas. For example, in linear probing with α = 0.9, an unsuccessful search needs ½ (1 + 1/0.12) = ½ (1 + 100) = 50.5 probes. In chaining the cost grows linearly with α. In linear probing the term 1/(1 − α)2 grows without bound as α approaches 1. When the table is half full, the difference between the two methods is small; at ninety percent full, an unsuccessful search in linear probing is about 27 times as expensive as in chaining.
The formulas are averages, and an actual table may deviate from them. In our example linear-probing table with α = 0.9, the average over successful searches was 2.44 probes; the formula gives 5.5. The difference comes from the fact that in the small example of nine keys most keys happened to be placed close to their own buckets. In the chaining table the average over successful searches is 14/9 ≈ 1.56, close to the 1.45 given by the formula.
Under the uniform hashing assumption, in a hash table whose load factor is kept below a constant α0 < 1, the average search time is O(1).
If α ≤ α0, the average number of probes is at most 1 + α0 in chaining and at most ½ (1 + 1/(1 − α0)2) in linear probing. Neither bound depends on n; both are constants. Computing the hash value also takes constant time when the key length is taken as constant. The total average cost is constant. □
The way to keep the load factor constant is to grow the table when it reaches a certain fullness. The common practice is this: when α exceeds a threshold such as 0.75, a new table twice the size is allocated and all keys are placed again in the new table. Since hash values depend on the number of buckets, the keys are not copied but rehashed. This takes O(n), but it is done rarely; as with doubling a dynamic array, the amortized cost per insertion is constant. Java's HashMap class uses a threshold of 0.75 by default.
The worst case, however, is O(n). A bad hash function can drop all keys into the same bucket. The search then scans a single long list or cluster; that is, it degrades to linear search. With the function h(x) = x % 10, keys such as 10, 20, 30, … all fall into bucket 0. In linear probing, clustering inflates the cost quickly as α approaches 1. If the table becomes completely full and the key is not in it, an empty bucket is never found, and the loop of hashSearch never ends.
Letting a linear-probing table fill up completely. Because hashSearch stops only at an empty bucket, searching for an absent key in a full table leads to an infinite loop. The load factor must be limited, or the loop must be stopped after at most m probes.
4.5Interpolation search
Binary search looks at the exact middle of the range whatever the key is. People do not search that way. When looking for "Yılmaz" in a phone book, you open the book near the end, not in the middle; for "Akın", near the front. Interpolation search puts this behavior into a formula.
4.5.1The idea: estimating the position
Interpolation search is used on sorted collections. It assumes that the values are spread at equal intervals across the range: the difference between consecutive items is about the same. Under this assumption the relation between index and value is close to a straight line. The position of the key is estimated on the line through the smallest and largest items of the range. The estimated position is probed. If the value does not match, the search continues, just as in binary search, in the narrower range to the left or right of the estimate.
The estimation formula comes from the equation of a line. The ends of the range are the points (lo, arr[lo]) and (hi, arr[hi]). On the line through these two points, the index of the point whose value is key is as follows:
The index to probe in interpolation search
pos = lo + (key − arr[lo]) · (hi − lo) / (arr[hi] − arr[lo])
is computed by the formula. The division is integer division; the result is rounded down.
The structure of the formula can be read intuitively. The ratio (key − arr[lo]) / (arr[hi] − arr[lo]) shows how far along the value range the key lies; it is a number between 0 and 1. Multiplying this ratio by the length of the index range, hi − lo, and adding it to lo gives the estimated position. If the key equals the smallest value the ratio is 0 and lo is probed; if it equals the largest value the ratio is 1 and hi is probed. Binary search can be thought of as a special case that always takes this ratio to be ½.
Searching for 70 in arr = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100}. lo = 0, hi = 9, arr[lo] = 10, arr[hi] = 100.
pos = 0 + (70 − 10) · (9 − 0) / (100 − 10) = 60 · 9 / 90 = 540 / 90 = 6
arr[6] = 70: found in a single probe. Because the distribution is exactly uniform, the estimate is perfect. Binary search probes indices 4, 7, 5, 6 in the same search and finds it on the fourth probe.
4.5.2Code: interpolationSearch()
int interpolationSearch(int[] arr, int n,
int key) {
int lo = 0, hi = n - 1;
while (lo <= hi && key >= arr[lo]
&& key <= arr[hi]) {
if (arr[hi] == arr[lo]) return lo; // avoid /0
long num = (long) (key - arr[lo]) * (hi - lo);
int pos = lo + (int) (num / (arr[hi] - arr[lo]));
if (arr[pos] == key) return pos;
if (arr[pos] < key) lo = pos + 1;
else hi = pos - 1;
}
return -1;
}lo and hi are again the bounds of the search range. The loop condition is richer than in binary search: the range must not be empty (lo <= hi), and the key must lie between the end values of the range (key >= arr[lo] and key <= arr[hi]). If the key is outside the ends, it cannot be in the range; the loop is not entered and −1 is returned. This check also guarantees that the estimated index stays inside the range. If the key were outside the ends, the ratio would come out smaller than 0 or larger than 1, and the index could fall outside the array.
The first line of the loop prevents division by zero. If arr[hi] == arr[lo], all values in the range are equal. Since the loop condition holds, the key equals this value too, and lo can be returned. Next the numerator and the index are computed. Writing the numerator and denominator separately fixes the order of operations explicitly: multiplication first, then division. If the division were done first, integer division would round the ratio down to 0 most of the time. Finally the value at the estimated index is probed. If equal, the index is returned. If smaller, the key is to the right: lo = pos + 1. If larger, the key is to the left: hi = pos − 1. If the range becomes empty or the key falls outside the ends, the loop ends and −1 is returned.
4.5.3Code trace: interpolationSearch(arr, 15, 24)
An array whose distribution is roughly, but not exactly, uniform is this:
arr = {10, 12, 13, 16, 18, 19, 20, 21, 22, 23, 24, 33, 35, 42, 47}, n = 15
The key is 24. The first eleven items of the array are dense, and the last four are sparse.
| Probe | lo | hi | Computation | pos | arr[pos] | Action |
|---|---|---|---|---|---|---|
| 1 | 0 | 14 | 0 + (24 − 10) · 14 / (47 − 10) = 196/37 | 5 | 19 | lo = 6 |
| 2 | 6 | 14 | 6 + (24 − 20) · 8 / (47 − 20) = 6 + 32/27 | 7 | 21 | lo = 8 |
| 3 | 8 | 14 | 8 + (24 − 22) · 6 / (47 − 22) = 8 + 12/25 | 8 | 22 | lo = 9 |
| 4 | 9 | 14 | 9 + (24 − 23) · 5 / (47 − 23) = 9 + 5/24 | 9 | 23 | lo = 10 |
| 5 | 10 | 14 | 10 + (24 − 24) · 4 / (47 − 24) = 10 + 0/23 | 10 | 24 | return 10 |
The first estimate is 196/37 ≈ 5.3, which rounds down to 5. arr[5] = 19 is smaller than the key; the search continues from index 6. With each probe the left end of the range rises, but the right end stays at 47. Because 47 is markedly larger than the rest of the array, it pulls the estimates to the left: the ratio is 4/27 in the second probe and 2/25 in the third. The search approaches the target step by step and finds 24 at index 10 on the fifth probe.
In this array binary search would find 24 in four steps, probing indices 7, 11, 9, 10. Here interpolation search is slower than binary search. Although the distribution of the array is "roughly uniform", the sparse values at the end have spoiled the estimates. The speed of interpolation search depends entirely on how uniform the distribution is.
4.5.4Complexity and the bad case
| Case | Order |
|---|---|
| Best | O(1) |
| Average (uniform distribution) | O(log log n) |
| Worst (skewed distribution) | O(n) |
| Extra memory | O(1) |
For keys that are uniformly and randomly distributed, the average number of probes is O(log log n). This result was proved by Perl, Itai and Avni in 1978. The proof is beyond the scope of these notes, but the intuition can be put as follows. In a uniform distribution the error of each estimate is of the order of the square root of the remaining range size. That is, the range shrinks with each probe from about n to √n: n → n1/2 → n1/4 → …. The number of steps needed for the range to shrink to constant size is of order log log n. Binary search takes the logarithm once; interpolation search takes it twice.
In numbers the difference is striking. For n = 106, log2 log2 n ≈ log2 19.93 ≈ 4.3, while binary search makes about 20 probes. But this gain has two costs:
- Each probe is more expensive than in binary search: instead of an addition and a division it contains a multiplication, a division and several subtractions. If reading from memory is slow, for example when the data is on disk, reducing the number of probes is worth this cost. If the data is in memory, the gain is often small.
- The intermediate product (key − arr[lo]) · (hi − lo) can overflow an
intfor large values. If the values are of order 109 and hi − lo is of order 106, the product is 1015, far beyond the limit 231 − 1. That is whynumin the code is alongand the multiplication is done inlong.
Searching for 9 in arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 1000}. The array is sorted, but the last item is much larger than the others.
- lo = 0: pos = 0 + (9 − 1) · 9 / (1000 − 1) = 72/999 → 0.
arr[0] = 1 < 9,lo = 1. - lo = 1: pos = 1 + (9 − 2) · 8 / 998 = 1 + 56/998 → 1.
arr[1] = 2 < 9,lo = 2. - In the same way the numerator always stays smaller than the denominator, and in each probe the index advances by only one: 2, 3, 4, 5, 6, 7.
- lo = 8: pos = 8 + 0 · 1 / 991 = 8.
arr[8] = 9: found.
The probed indices are 0, 1, 2, 3, 4, 5, 6, 7, 8: 9 probes. Interpolation search has degenerated into linear search. Binary search finishes the same search in 3 probes, with indices 4, 7, 8.
The source of the bad case is that the formula trusts the end values. A single outlier spoils all the estimates in the rest of the range. The same happens in an exponentially growing array, for example when searching for 32 in the array 2, 4, 8, …, 256: the estimates advance one at a time, 0, 1, 2, 3, 4. The worst case is O(n). That is why interpolation search is used on numeric keys whose distribution is known and uniform. Sequential ID numbers or timestamps taken at regular intervals are good examples. In practice, hybrid methods that mix interpolation steps with binary search steps are also used; this keeps the worst case at O(log n).
Skipping the end-value check in interpolation search. If key >= arr[lo] && key <= arr[hi] is removed from the loop condition, then for a value outside the range the index comes out negative or greater than hi, and an out-of-bounds access error occurs. If the check arr[hi] == arr[lo] is forgotten, a range whose items are all equal causes a division by zero.
4.6Jump search
Binary search makes big leaps inside the array: from the middle to a quarter, from there to an eighth. If the data is in memory, these leaps cost nothing. But in some environments going backwards, or jumping to a distant position, is expensive. Jump search is designed for such environments.
4.6.1The idea: advancing in blocks
Jump search works like a hurdler clearing hurdles as they run; the array must be sorted. The list is divided into blocks of size m, and the block size is usually chosen as m = √n. A big step is taken from the beginning of the list, and the item at that position, the last item of the block, is checked. If this item is smaller than the key, the key cannot be in this block; we jump to the next block. If the last item of the block is larger than or equal to the key, the key, if present, is in this block. The search returns to the start of that block and searches linearly inside it.
Going back does not require big leaps as in binary search. The data is always read forward; only once, in the last block, do we step back at most m steps. That is why jump search is preferred in environments where going backwards is expensive. A magnetic tape is read quickly forward, and rewinding is slow. A large file on disk is read in blocks; each block read is expensive, and the blocks that are skipped are never read.
4.6.2Code: jumpSearch()
int jumpSearch(int[] arr, int key,
int n) { // n ≤ arr.length
if (n == 0) return -1;
int block = (int) Math.sqrt(n);
int jump = block, pos = 0;
while (arr[Math.min(jump, n) - 1] < key) {
pos = jump; jump += block; // jump
if (pos >= n) return -1;
}
while (arr[pos] < key) { // linear
pos++;
if (pos == Math.min(jump, n)) return -1;
}
if (arr[pos] == key) return pos;
return -1;
}The jump distance is computed with Math.sqrt(n) and converted to an integer; block is ⌊√n⌋. pos marks the start of the current block and jump the start of the next block. The last item of the block is arr[jump − 1].
The first loop skips blocks. In each iteration the last item of the block is examined. The expression Math.min(jump, n) keeps us from running off the array when the last block is not completely full; in that case the last item of the array is examined. If the last item of the block is smaller than the key, the key is not in this block: pos moves to the start of the next block and jump one block ahead. If pos has passed the end of the array, the key is larger than all items of the array and −1 is returned.
When the first loop ends, the key, if present, lies in the range [pos, jump). The second loop scans this range linearly. As long as the scanned item is smaller than the key, pos increases by one. If the end of the block is reached, the key is not in this block and −1 is returned. The loop stops at an item that is not smaller than the key. The check on the last line looks at whether this item equals the key: if so the index is returned, otherwise −1.
4.6.3Code trace: jumpSearch(arr, 69, 10)
The array has ten items: {2, 9, 30, 32, 38, 47, 61, 69, 79, 81}. The key is 69.
- n = 10 →
block = ⌊√10⌋ = 3;jump = 3,pos = 0. arr[min(3, 10) − 1] = arr[2] = 30 < 69→ jump one block:pos = 3,jump = 6.arr[min(6, 10) − 1] = arr[5] = 47 < 69→ jump one block:pos = 6,jump = 9.arr[8] = 79 ≥ 69→ the jumping ends. The key may be in the block[6, 9).- Linear scan:
arr[6] = 61 < 69→pos = 7; 7 is not equal to 9, the end of the block. arr[7] = 69is not smaller than the key, and the loop stops. In the final checkarr[7] == 69is true; the method returns 7.
The probed indices are 2, 5, 8, 6, 7 in that order: 5 probes. After looking at index 8 the search returned to 6; this is the only step back in the search.
An unsuccessful search goes similarly. If 50 is searched for in the same array, indices 2, 5 and 8 are examined; since 79 ≥ 50, we move to the block [6, 9). arr[6] = 61 is already larger than 50, so the linear loop never runs. In the final check 61 ≠ 50, so −1 is returned. The probed indices are 2, 5, 8, 6.
4.6.4Why √n?
With block size m, the worst-case number of probes is found as follows. In the jumping phase at most n/m block ends are examined. In the linear phase at most m − 1 items inside the block are scanned; the last item of the block had already been examined. The total:
f(m) = n/m + (m − 1)
The two terms behave in opposite directions. If the blocks are small, the number of jumps grows; for m = 1 the search turns into linear search. If the blocks are large, the scan inside the block gets long; for m = n we again return to linear search. The best value is somewhere in between.
The function f(m) = n/m + m − 1 attains its minimum at m = √n. This value is 2√n − 1; hence the worst case of jump search is O(√n).
The derivative of f is f′(m) = −n/m2 + 1. Setting the derivative to zero gives m2 = n, that is, m = √n. Since the second derivative f″(m) = 2n/m3 > 0, this point is a minimum. Substituting gives f(√n) = n/√n + √n − 1 = 2√n − 1. □
The same result can be seen without derivatives. If the product of two positive numbers is fixed, their sum is smallest when the numbers are equal. The product of n/m and m is always n; so the sum is smallest when n/m = m, that is, when m = √n.
| n | m = √n | ≈ 2√n − 1 | Binary |
|---|---|---|---|
| 100 | 10 | 19 | 7 |
| 10,000 | 100 | 199 | 14 |
| 106 | 1,000 | 1,999 | 20 |
The complexity is O(√n): it lies between the O(n) of linear search and the O(log n) of binary search. The extra memory is O(1). Choosing the block size wrongly raises the cost noticeably. For n = 10,000, if m = 50 is chosen the worst case is 200 + 49 = 249 probes; with the best choice, m = 100, it is 199.
Once the block is found, it can be scanned in two directions. The code scans forward from the start of the block (6 → 7 in the search for 69). It could also have scanned backward from the end of the block (8 → 7). Either way makes at most m − 1 extra probes. One more improvement is possible: once the block is found, instead of a linear search inside it we can again jump (with steps of √m) or run binary search. But if binary search can be used, jump search is unnecessary from the start. Jump search makes sense only where going backwards is expensive.
4.7Exponential search
Binary search must know the length of the array; in its first step it assigns hi = n − 1. In some cases the length is unknown or very large. For example, a sorted data stream keeps getting longer, or reaching the end of a very large file is expensive. Exponential search first finds a range that contains the key, then runs binary search in that range.
4.7.1The idea: doubling the bound
Exponential search divides the sorted list into exponentially growing pieces. The bound, that is bound, is doubled at each step: 1, 2, 4, 8, 16, …. We stop when arr[bound] is larger than the key. At that moment the key, if present, is in the range [bound/2, bound], because the value at the previous bound, bound/2, was not larger than the key. Binary search is run in this range. The method is based on the search that Bentley and Yao proposed in 1976 for unbounded arrays.
In a list of 1024 items, let the key be around index 600. The bound passes through the values 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, and at all of them the value is smaller than the key. When the bound reaches 1024 we are outside the array and the doubling stops. The search continues with binary search in the range [512, min(1024, 1023)] = [512, 1023]. The doubling phase makes 11 tests (counting index 0), and binary search makes at most 10 probes in the range of 512 items.
The strength of the method is that the cost depends not on n but on the position i of the sought item. If the length of the array is unknown (unbounded or streaming data), or if the sought item is near the front, exponential search is ideal. If the key is at index 10, it does not matter whether the array has a million or a billion items; the search ends in a few steps.
4.7.2Code: exponentialSearch()
int exponentialSearch(int[] arr, int key, int n) {
if (n == 0) return -1;
if (arr[0] == key) return 0;
int bound = 1;
while (bound < n && arr[bound] <= key)
bound *= 2; // 1, 2, 4, 8, ...
int lo = bound / 2, hi = Math.min(bound, n - 1);
while (lo <= hi) { // binary search
int mid = (lo + hi) / 2;
if (arr[mid] == key) return mid;
if (arr[mid] < key) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}The method first checks index 0 separately, because the doubling starts at 1 and index 0 is never probed during doubling. Then bound = 1 is set. As long as arr[bound] <= key, bound is multiplied by 2. The condition bound < n keeps us from running off the array. At the end of the loop, bound marks the end of the range in which the key may lie, and bound / 2 its start. Because after the last doubling bound may have gone beyond the array, the upper limit is taken as Math.min(bound, n − 1). The remaining part is searched exactly as in iterative binary search.
If, in the last phase, a linear scan from bound / 2 onward had been used instead of binary search, the cost would have been O(i); if the key were absent, the scan would have gone to the end of the array. The length of the range is proportional to i, and searching it with binary search lowers the cost to O(log i).
4.7.3Code trace: exponentialSearch(arr, 47, 10)
The array is the one from the jump search example: {2, 9, 30, 32, 38, 47, 61, 69, 79, 81}. The key is 47.
| Phase | Index probed | Value | Decision |
|---|---|---|---|
| initial check | 0 | 2 | 2 ≠ 47 |
| doubling | 1 | 9 | 9 ≤ 47 → bound = 2 |
| doubling | 2 | 30 | 30 ≤ 47 → bound = 4 |
| doubling | 4 | 38 | 38 ≤ 47 → bound = 8 |
| doubling | 8 | 79 | 79 > 47 → stop; range [8/2, min(8, 9)] = [4, 8] |
| binary | 6 | 61 | mid = (4 + 8)/2 = 6; 61 > 47 → hi = 5 |
| binary | 4 | 38 | mid = (4 + 5)/2 = 4; 38 < 47 → lo = 5 |
| binary | 5 | 47 | mid = (5 + 5)/2 = 5; equal → return 5 |
In total 8 probes were made: 0, 1, 2, 4, 8, 6, 4, 5. Index 4 was looked at twice. The test 38 ≤ 47 was made during doubling, and binary search probed 4, the lower end of the range, again. The doubling phase had already shown that the value at index 4 is not larger than the key; this repetition would have been avoided had binary search been started with lo = bound / 2 + 1. In this array binary search finds 47 in 3 probes: if the key is not near the start of the array, exponential search is slower than binary search.
lo = hi = mid = 5 and 47 has been found.4.7.4Complexity
If the key is at index i ≥ 1, exponential search makes O(log i) probes. In the worst case (i ≈ n) the cost is O(log n), in the best case O(1); the extra memory is O(1).
Doubling stops when bound first exceeds i or reaches the end of the array. Since bound takes the values 1, 2, 4, …, this happens at the smallest k with 2k > i; that is k = ⌊log2 i⌋ + 1. The doubling phase looks at the positions 1, 2, …, 2k, that is, k + 1 positions. The range found is [2k−1, 2k] and contains at most 2k−1 + 1 ≤ i + 1 items. Binary search in this range makes at most about log2 i + 1 probes. The total of the two phases is about 2 log2 i, that is, O(log i). □
Exponential search is faster than binary search if the key is near the front, and about twice as slow if it is near the end. Table 4.16 compares the two methods for different positions in an array of a million items.
| i | Exponential (≈ 2 log2 i) | Binary (≈ log2 n) |
|---|---|---|
| 10 | ≈ 7 | 20 |
| 1,000 | ≈ 20 | 20 |
| 500,000 | ≈ 38 | 20 |
The break-even point is around i ≈ √n: the equation 2 log2 i = log2 n gives i = √n. For a million items this point is 1000, and the table shows it.
The main uses of exponential search are these: sorted lists of unknown length, records near the start of a large file, and sorted data streams. One application of the same idea is galloping search. When the Timsort algorithm merges two sorted arrays, a long stretch of one array sometimes comes before the other. Timsort finds the end of that stretch not item by item but by galloping search.
Taking the upper limit directly as bound instead of Math.min(bound, n − 1). After the last doubling, bound may exceed the length of the array; binary search then reads outside the array with arr[mid] and an ArrayIndexOutOfBoundsException is thrown. When 81 is searched for in the array of 10 items, doubling stops at bound = 16; if the limit is not clamped, the first midpoint is (8 + 16)/2 = 12.
4.8Comparison and choosing a method
Each of the seven methods is the best in some situation. To choose correctly, we first put the methods' costs side by side, and then see how they behave on the same data.
4.8.1Comparison table
| Algorithm | Precondition | Best | Average | Worst | Extra memory |
|---|---|---|---|---|---|
| Linear | none | O(1) | O(n) | O(n) | O(1) |
| Binary | sorted | O(1) | O(log n) | O(log n) | O(1) |
| Hash (table) | hash table | O(1) | O(1) | O(n) | O(m) |
| Interpolation | sorted, uniform | O(1) | O(log log n) | O(n) | O(1) |
| Jump | sorted | O(1) | O(√n) | O(√n) | O(1) |
| Exponential | sorted | O(1) | O(log i) | O(log n) | O(1) |
Three points should be kept in mind when reading the table. First, the average O(1) of a hash table depends on the load factor being kept constant; if the table is left to fill up, this guarantee is lost. Second, for the methods that need a sorted array, if the array is not sorted to begin with, a one-time sorting cost of O(n log n) is added. Third, the worst-case column is the guarantee the algorithm gives. A hash table and interpolation search are very fast on average, but give no guarantee against a bad input. Binary search is O(log n) on every input. This predictability makes it the default choice in most situations.
4.8.2Probe counts on the same array
The orders of growth speak of large n. It is also instructive to see how many probes the methods actually make on a small array. We use the ten-item array from the jump search and exponential search examples:
arr = {2, 9, 30, 32, 38, 47, 61, 69, 79, 81}
| Key | Linear | Binary | Jump | Interpolation | Exponential | Result |
|---|---|---|---|---|---|---|
| 69 | 8 (0–7) | 2 (4, 7) | 5 (2, 5, 8, 6, 7) | 1 (7) | 7 (0, 1, 2, 4, 8, 6, 7) | 7 |
| 47 | 6 (0–5) | 3 (4, 7, 5) | 5 (2, 5, 3, 4, 5) | 1 (5) | 8 (0, 1, 2, 4, 8, 6, 4, 5) | 5 |
| 2 | 1 (0) | 3 (4, 1, 0) | 2 (2, 0) | 1 (0) | 1 (0) | 0 |
| 50 | 10 (0–9) | 4 (4, 7, 5, 6) | 4 (2, 5, 8, 6) | 1 (5) | 8 (0, 1, 2, 4, 8, 6, 4, 5) | −1 |
A few lessons come out of the table. Because the array is almost uniformly distributed, interpolation search settles every query in a single probe. For 69 the estimate is 0 + (69 − 2) · 9 / 79 = 603/79 ≈ 7.6 → 7, which lands directly on the target. When 50 is searched for, interpolation search probes the 47 at index 5. Then lo = 6, and since the key is smaller than 61, the lower end of the new range, the loop ends immediately; the result is −1.
Binary search makes at most 4 probes per query; this is the bound ⌊log2 10⌋ + 1 = 4. Jump search varies with the block. When 47 is searched for, the last item of the second block is exactly 47, but the code does not stop at the block end; it goes back to the start of the block and scans indices 3, 4, 5. Exponential search shines when the key is at the start of the array: for 2, a single probe suffices. As the key approaches the end, the doubling and binary search phases together become more expensive than binary search. In the searches for 47 and 50, index 4 is probed twice: once in doubling and once in binary search.
In an array this small the differences are a few probes. As the array grows, the differences in order become decisive. With a million items, linear search makes half a million probes on average, jump search at most about two thousand, and binary search at most 20.
4.8.3Which algorithm when?
The choice depends on the properties of the data and the shape of the queries:
- Linear search: unsorted or small data, a linked list, a one-off search.
- Binary search: a sorted array and many queries; the general-purpose default.
- Hash table: exact-match queries only and many insertions and searches; order is not needed.
- Interpolation search: sorted and uniformly distributed numeric keys, for example sequential ID numbers.
- Jump search: sorted environments where going backwards is expensive, for example tape or a disk read block by block.
- Exponential search: a sorted list of unknown length, or cases where the key is near the start.
These rules can be turned into a sequence of questions. The first question is whether the data is sorted. If it is unsorted, there are two routes: linear search if one or a few searches will be made, or building a hash table if many searches will be made. If the data is sorted, the default choice is binary search. Interpolation search is considered if the distribution is uniform, exponential search if the length is unknown, and jump search if going backwards is expensive.
The choice is made as follows in three scenarios.
- A compiler's symbol table. Variable names are inserted and looked up all the time; order is not needed, only the question "is this name defined?" is asked. A hash table fits best: both insertion and search are O(1) on average.
- Prefix search in a dictionary application. All words that begin with "sea" are wanted. A hash table scatters the words, so it cannot help with this query. In a sorted array of words, first-position binary search finds the place where "sea" would be inserted, and reading proceeds forward from there.
- A sorted log file to which one record is added per second. The file keeps growing, and queries usually concern the most recent records. Running exponential search backward from the end of the file finishes in O(log i) cost since the sought record is near the end; the full length of the file does not even need to be known.
4.9Common mistakes
Search algorithms are short pieces of code, but they are very prone to mistakes. Most mistakes show up at boundary conditions and slip past tests made with small examples.
Binary search on an unsorted array. The program raises no error, but may return a wrong result. If 30 is searched for in {30, 10, 20}, the middle item is 10; since 30 is larger, the search goes right, the 20 is smaller, and −1 is returned. Yet 30 is at index 0. Binary, interpolation, jump and exponential search need a sorted array.
Off-by-one errors in the bounds. while (lo < hi) skips a single-item range. The assignment hi = mid may fail to shrink the range and can send the loop into an infinite run.
Overflow in the midpoint. In very large arrays (lo + hi) / 2 overflows and gives a negative index. lo + (hi − lo) / 2 does not overflow.
Division in interpolation search. If arr[hi] == arr[lo], there is a division by zero. If the key is outside the end values, the estimated index falls outside the array. The range must therefore be checked first.
A full hash table. If no empty bucket is left in linear probing, the search for an absent key never ends. The load factor must be limited, or the search must stop after m probes.
The bound in exponential search. If Math.min(bound, n − 1) is forgotten, an ArrayIndexOutOfBoundsException is thrown. If a linear scan is used instead of binary search in the last phase, the O(log i) cost is also spoiled and rises to O(i).
These mistakes share one lesson: once search code has been written, it must be tried on boundary cases. At the very least, the following cases should be tried: an empty array, a one-item array, the key being the first or last item, the key being smaller or larger than all values, and the key falling between two items. Since binary search is hard to write correctly, it is also a good habit in Java to use Arrays.binarySearch or Collections.binarySearch whenever possible.
4.10Summary
- The search problem: find the index of the key in an array; return −1 if it is absent. The cost is measured by the number of probes (comparisons).
- Linear search: compares one by one from start to end; no precondition. In a successful search it makes (n + 1)/2 comparisons on average and n in the worst case: O(n). On unsorted data there is nothing better.
- Sentinel linear search: by writing the key into the last cell it removes the
i < ntest from the loop; the number of comparisons drops from about 2n to n + 2, and the order does not change. - Binary search: compares with the middle item of a sorted array and eliminates half. It makes at most ⌊log2 n⌋ + 1 comparisons: O(log n). The iterative version uses O(1) and the recursive version O(log n) extra memory. A sorted array is an implicit balanced binary search tree.
- Details of binary search: the midpoint is computed as
lo + (hi − lo) / 2to avoid overflow; the bounds are updated by ±1; for the first position, the result is recorded on equality and the search continues to the left. - Hash search: computes the location with h(key). Collisions are resolved by linear probing or chaining. If the load factor α = n/m is kept constant, the average is O(1); the worst case is O(n). In linear probing, primary clustering inflates the cost quickly as α approaches 1.
- Interpolation search: estimates the position by proportion from the end values. It is O(log log n) on a uniform distribution and O(n) on a skewed one.
- Jump search: jumps over blocks of size √n, then searches linearly inside the block. The worst case is about 2√n − 1 probes, that is O(√n); it makes sense in environments where going backwards is expensive.
- Exponential search: doubles the bound 1, 2, 4, …, then runs binary search in the range [bound/2, bound]. The cost depends on the index of the sought item: O(log i). It is used on lists of unknown length and for searches near the start.
- Choosing: if the data is unsorted, linear search or a hash table; if sorted, binary search by default; interpolation on a uniform distribution, exponential for unknown length, jump search where going backwards is expensive.
4.11Key terms
- search problem
- probe
- best case
- average case
- worst case
- linear search
- sentinel
- binary search
- logarithmic
- divide and conquer
- decrease and conquer
- recurrence relation
- hash table
- hash function
- bucket
- collision
- open addressing
- linear probing
- primary clustering
- (separate) chaining
- load factor
- interpolation search
- jump search
- exponential search
4.12Test Yourself
The call
sentinelSearch(arr, 5, 9)runs onarr = {12, 5, 9, 20, 7}. What does the method return, and how many comparisons are made in total?Answer
The key 9 is written into the last cell as the sentinel, and
last = 7. After 12 ≠ 9 and 5 ≠ 9, the loop stops at the real 9 at index 2: 3 comparisons. 7 is put back.i < n − 1, that is 2 < 4, is true; because of the short-circuit||the second condition is never tested. The method returns 2; 4 comparisons are made in total.Iterative binary search looks for 50 in the array
{4, 9, 13, 20, 26, 31, 40, 48, 55, 61, 77}. Which indices are probed? When the loop ends, what areloandhi, and what doesloindicate?Answer
The probed indices are 5 (31 < 50,
lo = 6), 8 (55 > 50,hi = 7), 6 (40 < 50,lo = 7) and 7 (48 < 50,lo = 8). The loop ends withlo = 8,hi = 7and returns −1.lois the position at which 50 would be inserted without breaking the order: index 8, between 48 and 55.In the call
firstIndex({1, 3, 3, 3, 3, 3, 8}, 3), what are the values ofmidandresultin each iteration? Which indices does the version that finds the position of the last 3 probe on the same array?Answer
Iteration 1:
mid = 3, equal,result = 3,hi = 2. Iteration 2:mid = 1, equal,result = 1,hi = 0. Iteration 3:mid = 0, 1 < 3,lo = 1. The loop ends and 1 is returned. The last-position version goes right on equality withlo = mid + 1: it probes indices 3, 5, 6 and returns 5. The value 3 occurs 5 − 1 + 1 = 5 times.The keys 15, 22, 8, 29, 3 are inserted in order into an empty table with m = 7, h(x) = x % 7 and linear probing. What is the final table? Then, how many buckets are probed when 36 is searched for?
Answer
15, 22, 8 and 29 all fall into bucket 1: 15 → 1, 22 → 2, 8 → 3, 29 → 4 (probes 1, 2, 3, 4). The bucket of 3 is 3, but 3 and 4 are full; 3 goes into 5. The table becomes
[—, 15, 22, 8, 29, 3, —]. For 36, h = 1: the keys in buckets 1, 2, 3, 4, 5 are passed and the search stops at the empty bucket 6. There are 6 probes, and the result is −1.If the same five keys are inserted into a chaining table with m = 7 buckets, what is the load factor and which lists are formed? How many keys are compared when 36 is searched for?
Answer
α = 5/7 ≈ 0.71. The list of bucket 1 is 15 → 22 → 8 → 29, that of bucket 3 is only 3; the other buckets are empty. When 36 is searched for, the 4 keys in the list of bucket 1 are compared and the list ends. In this example chaining is slow too: the source of the problem is that the hash function gathers the keys in a single bucket, not the collision resolution method.
On the array 5, 10, 15, …, 100 (20 items), in how many probes does interpolation search settle the searches for 65 and for 63? Which indices does binary search probe for 65?
Answer
65: pos = 0 + (65 − 5) · 19 / 95 = 1140/95 = 12,
arr[12] = 65; 1 probe. 63: 58 · 19 / 95 = 1102/95 ≈ 11.6 → 11,arr[11] = 60 < 63,lo = 12. Now 63 < arr[12] = 65, so the loop ends: 1 probe, result −1. Binary search probes indices 9, 14, 11, 12 for 65: 4 probes.In jump search, what are the best block size and the worst-case probe count for n = 25 and n = 400? What happens if the block size is mistakenly chosen as 10 for n = 400?
Answer
n = 25: m = 5, 25/5 + 4 = 9 probes. n = 400: m = 20, 20 + 19 = 39 probes. If m = 10 is chosen, it is 400/10 + 9 = 49 probes; 10 more than the best choice.
In an array of a million items,
arr[i] = 2i. Which indices does exponential search probe while looking for 74 (index 37)? How many probes would binary search make at most?Answer
First index 0: 0 ≠ 74. Doubling finds values smaller than 74 at indices 1, 2, 4, 8, 16, 32, and at index 64 the value is 128 > 74 and it stops. The range is [32, 64]. Binary search probes indices 48, 39, 35, 37 and finds 37. In total 12 probes: 0, 1, 2, 4, 8, 16, 32, 64, 48, 39, 35, 37. Binary search would have made at most ⌊log2 106⌋ + 1 = 20 probes.
With
lo = 1,500,000,000andhi = 1,600,000,000, what do(lo + hi) / 2andlo + (hi - lo) / 2give in Java?Answer
The true sum is 3,100,000,000 and exceeds 231 − 1. The
intsum becomes 3,100,000,000 − 232 = −1,194,967,296; halved, it gives −597,483,648, and the accessarr[mid]throws anArrayIndexOutOfBoundsException. The safe form gives 1,500,000,000 + 50,000,000 = 1,550,000,000.
4.13Further reading
- R. Sedgewick and K. Wayne, Algorithms (4th ed., 2011), Sections 3.1 and 3.4: present a symbol table built on binary search in a sorted array, and hash tables (separate chaining, linear probing), with Java code and empirical measurements.
- D. E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching (2nd ed., 1998), Sections 6.1, 6.2.1 and 6.4: give sentinel search, the history of binary search and the derivation of the linear-probing formulas in detail.
- J. Bentley, Programming Pearls (2nd ed., 2000), Columns 4 and 5: work through writing binary search correctly and justifying its correctness as an example.
- J. Bloch, “Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken”, Google Research Blog, June 2, 2006: a short article on how the midpoint overflow bug was discovered in the Java library.
4.14References
- J. L. Bentley, A. C. Yao, “An Almost Optimal Algorithm for Unbounded Searching”, Information Processing Letters 5(3), 1976.
- J. Bentley, Programming Pearls, 2nd ed., Addison-Wesley, 2000.
- J. Bloch, “Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken”, Google Research Blog, 2006.
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022 (Sections 2.3, 11).
- D. E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching, 2nd ed., Addison-Wesley, 1998.
- Y. Perl, A. Itai, H. Avni, “Interpolation Search — A Log Log N Search”, Communications of the ACM 21(7), 1978.
- R. Sedgewick, K. Wayne, Algorithms, 4th ed., Addison-Wesley, 2011 (Sections 3.1 Binary search, 3.4 Hash tables).
- B. Shneiderman, “Jump Searching: A Fast Sequential Search Technique”, Communications of the ACM 21(10), 1978.
Related pages: Chapter 4 slides · © Sercan Külcü. All rights reserved.