A frequent requirement for many programs is to search a list for a given item. The two most common basic methods of searches are sequential searches and binary searches.
In a sequential search, each item in a list is examined in the order in which it occurs in the list until the desired item is found or the end of the list is reached. The main advantage to a linear sort is that the list does not need to be sorted before searching. The main disadvantage is that it is an inefficient search.
Essentially, a linear search says For all the items in the list, compare the item to the desired value. If the value is found, return the location of the item. Otherwise, return a flag value indicating that the item was not found.
using namespace std;
//returns -1 if the value is not found
int linearSearch(int list[], int bounds, int searchValue);
void displaySearchValue(int theList[], int index);
int main(){
int theList[] = { 4, 8, 15, 16, 23, 24, 3, 5, 17, 257};
int bounds = sizeof(theList) / sizeof(int);
int searchValue = 10;
int rValue = linearSearch(theList, bounds, searchValue);
displaySearchValue(theList, rValue);
searchValue = 5;
rValue = linearSearch(theList, bounds, searchValue);
displaySearchValue(theList, rValue);
return 0;
}
void displaySearchValue(int theList[], int index){
if(index < 0){
cout << "The value was not found" << endl;
} else {
cout << "The value was found at [" << index << "] and is " << theList[index] << endl;
}
}
int linearSearch(int list[], int bounds, int searchValue){
//go backwards through the array to find the value
for(int i = bounds; i > -1; i--){
if(list[i]==searchValue){
return i;
}
}
//return a negative value;
return -1;
}
As has already been mentioned, the big advantage to linear searches is that the list does not have to be in sorted order to perform the search. Another advantage is that if the item is found relatively early in the search, then the inefficiency of the searching algorithm is not as big of a concern.
In a binary search, the list is required to be in sorted order. Starting in the middle, we compare the item to the desired value. One of three possible results can come from this comparison – either the desired item is found, or the desired value may be greater or less than the middle value. If the desired item is greater than the middle element, if it is in the list we know it must be in the half that comes after the middle value. Likewise, if the desired item is less than the middle element, we know that the element must be in the half that comes before the middle value.
The binary search algorithm functions be first setting the lower index to 0. It then sets the upper index to one less than the size of the list. We then begin with the first item in the list. We search while the lower index is less than or equal to the upper index. In this loop, we set the midpoint index to the integer average of the lower and upper index values. We compare the desired key value to the midpoint element. If the element is found, we return the index value of the current item. Otherwise, if the desired element is greater than the midpoint element, we set the lower index value to the midpoint value + 1, since we know the value must be in the range after the midpoint value. If the value is less than the midpoint element, we set the upper index to the midpoint value minus one.
using namespace std;
int binarySearch(int theList[], int bounds, int key);
void displayValue(int theList[], int index);
int main()
{
int ourValues[] = {1, 2, 3, 4, 5, 8, 15, 16, 17, 23, 32, 42, 64, 128, 404};
int searchValue = 5;
int found = binarySearch(ourValues, sizeof(ourValues) / sizeof(int), searchValue);
displayValue(ourValues, found);
return 0;
}
void displayValue(int theList[], int index){
if(index > 0){
cout << "Value found at index [" << index << "] (" << theList[index] << ")" << endl;
} else {
cout << "Value not found" << endl;
}
}
int binarySearch(int theList[], int bounds, int key){
int lower, upper, mid;
lower = 0;
upper = bounds - 1;
while(lower <= upper){ mid = (int)((lower + upper) / 2);
if(theList[mid]==key){ return mid; }
else if(key > theList[mid]){
lower = mid + 1;
} else {
upper = mid - 1;
}
}
return -1;
}
The great thing about the binary search is that the number of items to search through is halved each time through the search loop. In general, after p passes through the search loop, the number of values remaining to be searched is N / (2 ^ p).
One of the simplest sorting techniques is the selection sort. In a selection sort, the smallest value is initially selected from the complete list of data and switched with the first element on the list. Once the smallest value is sorted, the next pass needs to only consider the second through the last elements.
using namespace std;
void printList(int theList[], int bounds);
void selectionSort(int theList[], int bounds);
int main()
{
int aList[] = {404, 10538, 3, 5, 17, 257, 451, 80, 443, 1729, 1701, 1138, 47};
int bounds = sizeof(aList) / sizeof(int);
printList(aList, bounds);
selectionSort(aList, bounds);
printList(aList, bounds);
return 0;
}
void printList(int theList[], int bounds){
cout << endl;
for(int i = 0; i < bounds; i++){
cout << theList[i] << "\t";
}
cout << endl;
}
void selectionSort(int theList[], int bounds){
int i, total, remaining, smallest, tmp, minimumIndex;
total = bounds - 1;
for(i = 0; i < total; i++){
minimumIndex = i;
for(remaining = i + 1; remaining < bounds; remaining++){
if(theList[remaining] < theList[minimumIndex]){
minimumIndex = remaining;
}
}
//check if anything needs to be moved
//if so, swap the values;
if(minimumIndex != i){
tmp = theList[i];
theList[i] = theList[minimumIndex];
theList[minimumIndex] = tmp;
}
}
}
Simple C++ Tutorials 