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 to search for the name provided...
