Chapter 9, Problem 19RQE

Explanation of Solution

Linear search:

• Linear search or sequential search is the process of searching the particular element in the array one by one until the searching element is found.
• Here, it uses the loop iteration to start from the beginning of the array to the last element until it finds out the searching element.
• This searching process is continued till the last element until the searching element is found from the array.
• If the searching element is not present in the array, then the search process returns the message according to unsuccessful search.

Number of comparison in linear search:

To search the target element that is present in the array, the search element is compared with the number of elements present in the array. Even if the array contains 500 elements, the search process continues 500 times, if the search element is present at the end of the array.

Maximum number of comparison = N

Average number of the comparison = N / 2

Binary search:

• Binary search is a special search process that searches for the particular element present in the array. It starts searching from the middle towards the left or right until the search element is found.
• Initially from the given array, find out the middle element of the array and then check whether the middle element is larger or smaller than the searching element and continue the following steps based on the condition,
  • If the search element is larger, it will search towards the right of the array.
  • If the search element is smaller, it will search towards the left of the array.
• Since the searching process is continued either in left or right direction and it leaves any part of the array for comparison based on the condition satisfied...