Searching Algorithms: Revision Notes (Computer Science A 4.14)

Full explanation, figures and traced examples: Topic 4.14 study guide.

Recap

Linear search checks each element in order until the target is found or all elements have been checked. It may start from either end. It works on unsorted data. The standard method returns the index of the first match from inside the loop and returns -1 after the loop.

for (int i = 0; i < a.length; i++)
{
    if (a[i] == target) { return i; }
}
return -1;

For objects such as Strings use list.get(i).equals(target). For a 2D array search each row, or nest the loops and return inside the inner loop.

Key relationships

Idea	Rule
Result	index of the first match, or -1
Best case	1 comparison (target first)
Worst case	n comparisons (target last or absent)
Successful search	index + 1 comparisons when searching from the front
Unsuccessful search	exactly n comparisons
Data order	any order; no sort needed
From the end	i from length - 1 down to 0; finds the last match
Strings and objects	equals, not ==
2D array	search each row; return a row (or row and column)
Count all matches	no early return; add to a counter

Assumptions

• The collection is not null; an empty collection returns -1.
• The test (equality or a property) can be applied to every element.
• For a 2D array the table is rectangular.

A mini-example to rehearse

For a = {7, 3, 9, 3, 5}: target 9 gives index 2 after 3 comparisons; target 3 gives index 1 after 2 comparisons (the second 3 is never reached); target 4 gives -1 after 5 comparisons. Searching from the end for 3 gives index 3. A buggy loop that returns -1 in an else branch returns -1 for target 9, even though 9 is present.

Mistakes to avoid

1. Returning -1 inside the loop.
2. Returning the element instead of its index.
3. Comparing Strings with ==.
4. Writing i <= a.length.
5. Expecting linear search to need sorted data.
6. Counting the wrong number of comparisons for an unsuccessful search (it is n, not n - 1).

How this topic is usually tested

• Trace a search and give the returned index or -1.
• State how many comparisons a given search makes.
• Identify the bug in a search method.
• Write a search for an array, an ArrayList or a row of a 2D array.

Quick self-check

1. Search {7, 3, 9, 3, 5} for 3: result and comparisons? Index 1, 2 comparisons.
2. Search the same array for 4: result and comparisons? -1, 5 comparisons.
3. Where must return -1 go? After the loop.
4. Which method compares Strings by their characters? equals
5. Does linear search need sorted data? No.