Example

Consider the problem of finding a key in an array. An example is presented below.

arr -> [71 86 79 36 78 35 75 86 24 11]
        0  1  2  3  4  5  6  7  8  9

key: 75

There are 2 common variations:

• Return the position of key in arr or -1 if key is not in arr.
• Return true if key is in arr; otherwise, return false.

In the case of an element that appears in arr more than once (such as 86 in the example) some implementations explicitly return the position of the first occurrence while others may return the position of any occurrence.

Sequential/linear search algorithm

If nothing is known about the order of the elements in the array, we use a sequential/linear search. We check each element, starting with the first, against the given key. If we find an element that matches the key, we stop and return the desired value. If we get to the end of the array and we have not found the key, we return the value that indicates that the key was not found (typically -1 or false).

Iterative implementations

int return

public static int search(int[] arr, int key)
{
    for (int i = 0; i < arr.length; i++)
		if (arr[i] == key)
			return i;

	return -1;
}

boolean return

public static boolean search(int[] arr, int key)
{
    for (int i = 0; i < arr.length; i++)
		if (arr[i] == key)
			return true;

	return false;
}

Recursive implementation

// returns the position of key in arr[startIndex] ... arr[arr.length - 1]
// or -1 if key is not in arr[startIndex] ... arr[arr.length - 1]
private static int search(int[] arr, int key, int startIndex)
{
    if(startIndex >= arr.length)
        return -1;
    
    if(arr[startIndex] == key)
        return startIndex;
    
    return search(arr, key, startIndex + 1);
}

public static int search(int[] arr, int key)
{
    return search(arr, key, 0);
}

search(int[], int, int) is a private recursive helper method. We use recursive helper methods when the parameters for the recursive method differ from those we want for the public method. search(int[], int) calls the helper method, with 0 as startIndex, and returns the result.

Variants

These variants are not suggestions. The implementations above are better.

With extra variable

public static int search(int[] arr, int key)
{
	int keyIndex = -1;
	
    for (int i = 0; i < arr.length; i++)
		if (arr[i] == key)
			keyIndex = i;

	return keyIndex;
}

This variant unnecessarily stores the position of key in keyIndex. This is not a good thing. It executes more statements than necessary when key is in arr more than once. The extra complexity also increases the chance of an error.

If we specifically want to find the last occurrence of key in arr, we should loop through arr backwards instead.

With sorted array and early return

// precondition: arr is sorted
public static int search(int[] arr, int key)
{
	for(int i = 0; i < arr.length; i++)
	{
		if(arr[i] == key)
			return i;
		else if(arr[i] > key)
			return -1;
	}
	
	return -1;
}

This variant stops when it finds a value in arr that is greater than key. If arr is sorted (in increasing/non-decreasing/smallest to largest order) and a value greater than key is found before key, key is not in arr.

This variant can be written in numerous ways, including with a while loop.

As with the other variant, this is not something that would generally be done in practice. If we know arr is sorted, binary search is a better choice.

AP CS A Exam sort & search algorithms

• Binary search
• Selection sort
• Insertion sort
• Merge sort

Comments

Comment on Sequential/linear search