Searching
Information storage is big business. Along with storage, comes the need to access information in a variety of ways. One of the more common access methods is that of searching. We search all the time on Google, accessing their extensive database of web pages and content. On a smaller scaler, we have been writing programs that store significant amounts of information in arrays. Often, we need to search through an array to locate the index of a given item (a student id, a specific score, etc.). In the case of parallel arrays of related information, finding the index of one item provides us with lots of other information about that thing.
There are a variety of search algorithms available for use. Different algorithms excel in different situations. This type of decision making is often discussed in a data structures course and involves informal analysis tools such as best/worst case scenarios as well as formal analysis tools such as Big O Notation. Big O is a method of characterizing the nature of an algorithm in terms of the number of comparisons that need to be run. More on this later.
Sequential Search
Sequential Search is a very simple algorithm for searching an array. In sequential search, each element of the array, in order, is checked against the target. The best case sencario is that the target is in the first slot of the array. The worst case scenario is that the target is either in the last slot OR not in the array. Most searching algorithms return the index of the target in the structure or -1 if the target is not found. In terms of Big O, sequential search is looked aat as a linear timed algorithm or O(n). This means that as the size of the data structure grows, the average number of comparisons grows at the same rate.
The basic code for a sequential search is as follows:
<![CDATA[int [] arr={4,6,3,7,8};
int target=7;
int foundIndex=-1;
for(int x=0; x<arr.length; x++){
if(target==arr[x]){
foundIndex=x;
break;
}
}]]>
In this case, the search terminates when the item is found, thus returning the first occurence of the item. By removing the break statement, or by traversing the array in reverse order, we could easily return the last occurence of the item.