Array Algorithms

Arrays are often used to deal with large data sets. The following are some common algorithms involving arrays

Finding the Largest Value in an Array:

Finding the largest (or smallest) value in an array can be done by a process that you can think of as "king of the hill". We initialize a variable to the biggest value that we have met so far (first element in the array). This is basically our "king". We then run through the array and everytime we see a bigger value we replace the king with this new value.

int biggest(int array[], int used)
{
	int i;
	int biggestSoFar = array[0];
	for (i = 1; i < used; i++){
		if(array[i] > biggestSoFar){
			biggestSoFar = array[i];
		}
	}
	return biggestSoFar;
}

Here is an animation showing how this works:

Linear Search

The linearSearch() function finds and returns the index of the key value from the array with used values stored. Note that the capacity of this array can potentially be larger than used. This algorithm starts by setting the return value (rc) -1 indicating that the key is not in the array. We then iterate through the array. If we find a match, we alter the return value to the the current index (i). Changing the return value to any valid index will invalidate the first part of the continuation condition and immediately cause the function to stop.

int linearSearch(int key, int array[], int used)
{

	int i;
	int rc = -1;
	for (i = 0;rc == -1 && i<used;i++){
		if (array[i] == key){
			rc = i;
		}
	}
	return rc;
}

Here is an animation of how this code works: