Chapter 8, Problem 18RQE

Explanation of Solution

Linear search:

• Linear search or sequential search is the process of searching for a particular element that is present in the array one by one till the last element in the search element is found.
• The search uses a loop that iterates from the beginning till the last element to find the search element.
• The search continues for all the elements present in the array until the last element.
• The search of the target element is made after comparing it with each and every element that is present in the array.
• The search process continues until the target value or search value is found.
• If the search element is not found, the search gets returned unsuccessfully.

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 smart search process that searches for the particular element that is present in the array from the middle towards the left or right until the search element is found.
• The search element is searched from the middle as the elements present in the array need to be present in the sorted order.
  • 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.
• The search continues in a narrow way such that it searches for a quarter of the array until there are no values left in the array to search or compare.
• The search of the target element is made in a smart way it eliminates a portion of an array based on the given element, as the array is sorted...