Searching - sheerazwalid/COMP-I GitHub Wiki
Linear search
When the items in an array are not in order, finding a particular value needs to be with linear search. This means, each item needs to be examined one after another until you either find the value you are looking for of determine that the value is not present.
For example, suppose the array where a = [3, 9, 2, 11, -2]. If we were given a value k to find in a, we would compare k with 3, then 9, then 11, then -2. If k where equal to 9, then the search would stop after the second comparison. If k were 12, then the search would require 5 comparisons to determine that k is not in a. So in the worst case scenario, if there are n values in the array, then it would take n comparisons to determine that k is not in a. As the size of the array increases, the amount of work needed to locate k in a in the worst case increases proportionately.
The following is a function that finds an integer k in an array a containing n integers.
int linearSearch(int a[], int n, int k) {
for (int i = 0; i < n; ++i) {
if (a[i] == k) return i;
}
return -1;
}
When k is in a, the function linearSearch returns the position of k in a. When k is not in a, then linearSearch returns -1.
Returning -1 to indicate that a value is not in an array is the common convention used by programmers, probably because -1 is the simplest number that is not a valid index.
Binary search
When the items in an array are in order, finding a particular value can be done efficiently with a process called binary search. This process resembles looking up a name in a phone book or a word in a dictionary. One looks up a name in a phone book by successively shrinking a range of pages until you arrive at a single page with the name on it or can determine that the name is not in the book.
As an example, take the array fro the linear search example and rearrange the values so they are in increasing order. The result is a = [-2, 2, 3, 9, 11]. If we were given a value k to find in a, we could start by comparing k with the value 3 because it is in the middle of the array. If k is equal to 3, then we found k in a and we are done. If k is smaller than 3, then we would narrow the search to the sub-array [-2, 2]. If k is larger than 3, we would marrow the search to [9, 11]. After narrowing the search, you could apply the same process tot he sub-array. You can imagine how this would work for a large sequence of values that are in order; you successively half the sequence until you arrive at the value.
The following is a function that finds an integer k in an array a containing n integers.
int binarySearch(int a[], int n, int k) {
int s = 0;
int e = n - 1;
while (s <= e) {
int m = (s + e) / 2;
if (k == a[i]) return i;
else if (k < a[i]) e = m - 1;
else if (k > a[i]) s = m + 1;
}
return -1;
}