Explain

(i) Linear search method,

(ii) Binary search method.

Which of the two is more efficient for sorted data ?

(i) Linear Search — Linear Search refers to the searching technique in which each element of an array is compared with the search item, one by one, until the search-item is found or all elements have been compared.

For example, consider an array

int arr[] = {5, 8, 11, 2, 9};

and the search item 2. Linear search will compare each element of the array to 2 sequentially until either the search value 2 is found or all the elements have been compared.

(ii) Binary search — Binary Search is a search-technique that works for sorted arrays. Here search-item is com­pared with the middle element of array. If the search-item matches with the element, search finishes. If search-item is less than middle (in ascending array), we perform binary-search in the first half of the array, other­ wise we perform binary search in the second half of the array.

For example, consider an array

int arr[] = {2, 5, 8, 11, 14};

and the search item 11. First, the search value will be compared with the middle value 8. Since the values are not equal, binary search will be performed in the latter half of the array, i.e., {11, 14}. The search value will be compared with the mid value, which will be 11. Since search value is found, binary search will stop.

Binary search is more efficient than linear search as it searches the given item in minimum possible comparisons.