Page 258 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Unit 14: Searching

Notes

Notes Remember that in programming languages like C, arrays of length N have indices
numbered 0 through N–1; therefore a return value of –1 cannot be valid place in the array
and the calling function will know that the value wasn’t found.
We declare our function as follows:
int sequential_search(int arr[], int n, int value);
Step 1: We need to search through every element in the array. This can be easily accomplished
using a loop.
for(i=0; i<n; i++) {
...
}
Step 2: At every place in the array, we need to compare the array element to the value we’re
searching for. If this index stores the value, then immediately return the correct answer. Otherwise,
keep going.
for(i=0; i<n; i++) {
if (arr[i] == value) return i;
}
Step 3: What happens if the value is never found? The loop will end and the function will
continue. So after the loop we need to return the value –1.
for(i=0; i<n; i++) {
if (arr[i] == value) return i;
}
return -1;
Step 4: Putting this all together we end up with a function to do a linear search of an array:
int sequential_search(int arr[], int n, int value) {
int i;
/* loop through entire array */
for(i=0; i<n; i++) {
/* if this element contains the value being searched for,
* return the location in the array
*/
if (arr[i] == value) return i;
}
/* if we went through the entire array and couldn’t find
* the element, return –1. as 0 is the smallest index in
* the array, –1 represents an error and tells the calling
* function that a value wasn’t found
*/
return –1;
}

LOVELY PROFESSIONAL UNIVERSITY 251