UoL CS Notes
Menu

Arrays - Sequential Search

COMP108 Lectures

For arrays, out of bounds means any index that is not in the range of the index.

When using arrays in pseudo code the following notation will be used:

arrayName[index]

Arrays in the notes will also be indexed from 1.

Input

$n$ numbers stored in an array A[1..n], and a traget number key.

Output

Determine if key is in the array or not.

Algorithm

  1. From i = 1, coparte key with A[i] one by one as long as i <= n.
  2. Stop and report "Found" when key is the same as A[i].
  3. Repeat and report "Not Found" when i > n.

Example

12 34 2 9 7 5
7          
12 34 2 9 7 5
  7        
12 34 2 9 7 5
    7      
12 34 2 9 7 5
      7    
12 *34 2 9 7 5
        7  

Found

Pseudo Code

i = 1
found = false
while i <= n AND found == false
begin
	if A[i] == key then
		found = true
	else
		i = i + 1	// Don't increment if number is found to save i.
end
if found == true then
	output "Found"
else
	output "Not Found"

Time Complexity

How many comparisons does this algorithm take?

  • Best case:
    • The best case is where the key is the first element in the list.
    • $O(1)$
  • Worst case:
    • The worst case is where the key is not in the array or the key is the last number.
    • $O(n)$