Chapter 5. Efficient Searching – Binary Search and Sorting
What is searching? Searching is trying to locate a given value in a collection of values. For example, you are given an array of integers, and your problem is to check whether the integer 5 is in that array. This is a search problem. In addition to just deciding whether the element 5 is in the array, we may be interested in its location as well when it is found. This is also a search problem.
Another interesting take on it would be to imagine a dictionary, that is, an array of values and associated values. For example, you have an array of names of students and their marks, as shown in the following table:
|
Name |
Marks |
|---|---|
|
Tom |
63 |
|
Harry |
70 |
|
Merry |
65 |
|
Aisha |
85 |
|
Abdullah |
72 |
|
… |
... |
The list continues. Suppose, our system lets the student view his/her own marks. They would type their name and the system would show their marks. For simplicity, let's assume that there are no duplicate names. Now, we have...
