Course Content
L1: Algorithm Decomposition and Abstraction
In this topic we will focus on the definition of: - Algorithm - Decomposition - Abstraction You will also decompose and develop abstraction from given problems.
0/2
L2: Developing Algorithms using Pseudocode
0/1
L3: Developing Algorithm using flowcharts
0/1
L4: Linear and Binary Search
0/1
L5: Bubble Sort
0/1
L6: Merge Sort
0/1
L7: Assessment
0/1
8525 Unit 1: Fundamentals of Algorithm

## Lesson 04: Linear and Binary Search

### Specification Points Addressed in this lesson:

• Understand and explain how the linear search algorithm works.
• Understand and explain how the binary search algorithm works.
• Compare and contrast linear and binary search algorithms.
• Understand that more than one algorithm can be used to solve the same problem.
• Compare the efficiency of algorithms explaining how some algorithms are more efficient than others in solving the same problem.

### 1. Linear Search

The Linear search algorithm

• Start at the beginning of the list
• Compare each element with the key
• IF they are the same THEN item found
• ELSE compare next element
• Repeat the comparison until we either find the element or reach the end of the list.
• If we are at the end of the list and the element is not found then the element is not in the list.

In the example below the key (3) was found after 6 comparisons. Here is the pseudo-code for the linear search algorithm.

``````SUBROUTINE linearSearch(key)
found ← FALSE
position ← 0

IF list[position] = key THEN
OUTPUT key, "found at position", position+1
found ← TRUE
ELSE
position ← position + 1
ENDIF

{if the key is not in the list}
IF position = LEN(list) THEN
OUTPUT key, "is not in the list"
ENDIF
ENDWHILE
ENDSUBROUTINE ``````

The input to the subroutine is the key – item that we are trying to find. The algorithm starts by creating a boolean variable called found and assigning the value FALSE to the variable; an integer variable called position is also created, and the value 0 is assigned to it.

The statements in the WHILE loop execute as long as we are not at the end of the list (position < LEN(list) ) AND we have yet to find the item. If one of those conditions is met, then the WHILE loop terminates.

In the WHILE loop, we use an IF statement to check if the item we are currently looking at is the same as the key. If they are the same, we print “found at position” and set the Boolean variable to True (this will break the WHILE loop).

If the key differs from the current item, we increment the position to move on to the next item in the list.

The last IF statement checks that if we get to the end of the list and have not found the item, we print a message to inform the user.

### 2. Binary Search

In general, the binary search is more efficient than the linear search on a larger list; however, the list must be sorted to use the binary search. Here is the algorithm for the binary search.

• Compare the key with the middle value
• If they are the same, stop; we have found our value
• If the middle value is greater than the key, then carry out the binary search on the bottom half of the list.
• If the middle value is less than the key, then carry out the binary search on the top half of the list.

Here is the pseudo-code for the binary search:

``````SUBROUTINE binarySearch(key)
low ← 0
high ← LEN(array) - 1

WHILE high >= low
midPosition ← (low + high) DIV 2
midValue ← array[ midPosition ]

IF (midValue < key ) THEN
low ← midPosition + 1
ELSE
IF (midValue > key) THEN
high ← midPosition - 1
ELSE
RETURN midPosition
ENDIF
ENDIF
ENDWHILE
RETURN -1 # not in list
ENDSUBROUTINE``````

### 3. Comparing Linear and Binary Search

• Binary search and linear search will both find an element in a list.
• Binary search only works on a sorted list, while linear search can work on any list.
• Binary search will find the element with fewer comparisons on average than linear search
• If the list is short, both algorithms perform at the same rate.

Exercise Files
1_4 Worksheet 1.pdf
Size: 108.90 KB
0% Complete
Scroll to Top