# Sequential/linear search for the AP CS A Exam

## 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.