Question

[12 marks] List all the steps used to search for 7 in the sequence: 1, 3, 4, 5, 6, 8, 9, 11 for both a linear search and a binary search.

Answer 1

In Linear Search, the element to be searched is checked sequentially with each element within the array or the list until a match is found or the whole array or the list has been searched.

Linear Search :

Step 1 : Start from the leftmost element, i.e 1. Since 7 is not equal to 1, so move further.

Step 2 : Now, compare next element i.e 3. Since 7 is not equal to 3, so again move further.

Step 3 : Now again, compare next element i.e 4. Since 7 is not equal to 4, so move further.

Step 4 : Now, compare next element i.e 5. Since 7 is not equal to 5, so move further.

Step 5 : Now, compare next element i.e 6. Since 7 is not equal to 6, so move further.

Step 6 : Now, compare next element i.e 8. Since 7 is not equal to 8, so move further.

Step 7 : Now, compare next element i.e 9. Since 7 is not equal to 9, so move further.

Step 8 : Now, compare next element i.e 11. Since 7 is not equal to 11, so move further.

Step 9 : Since we have now searched the whole list, so search is finished and we saw that element is not found in the list. Hence, the search is unsuccessful. In programming language, we can say that if this condition occurs, return -1.

In Binary Search, the element to be searched is compared first with the middle element of the list or array. If they aren't equal, then it is decided that in which half the element will be present and the other half is eliminated. So for this, it is required that array or list should be sorted. This keeps on going until the target value is found and in the case if search ends or completed with remaining half being empty, then it means that search is unsuccessful or the element is not present in the array or list.

Binary Search :

Step 1 : Check whether the list is in sorted order or not. Clearly list is in sorted order, so now proceed to step 2.

Step 2 : First search for the middle element of the list.

mid = (beginning + last)/2 = (0 + 7)/2 = 7/2 = 3

So, middle element is 5. Since 7 is not equal to 5, so lets proceed to step 2 now.

Step 3 : Now since 7>3, it means that the element can be present in the second half of the list i.e 6,8,9,11. So neglect the first half, i.e 1,2,3 and proceed with second half.

Step 4 : Now finding the middle element in the second half.

mid = (beginning + last)/2 = (0 + 3)/2 = 3/2 = 1

So, middle element is 8. Since 7 is not equal to 8, so lets proceed to step 5 now.

Step 5 : Now since 7<8, it means that the element can be present in the first half of the list i.e 6. So neglect the second half, i.e 9,11 and proceed with first half.

Step 4 : Since only one element is left now, so no need to find any middle element further. Check whether it is equal to 7 or not. Since 6 is not equal to 7, this means that 7 is not present in the list.