Searching-Linear Search

Searching

Searching is an operation which finds the location of a given element in a list. The search is said to be successful or unsuccessful depending on whether the element that is to be searched is found or not.

Two Standard Searching Techniques are Linear Search and Binary Search

Linear Search

This is the simplest method of searching. In this method, the element to be searched is sequentially searched in the list. This method can be applied to a sorted or an unsorted list.

Searching in case of sorted list starts from 0th element and continues until the element is found or an element whose value is greater (assuming the list is sorted in ascending order) than the value being searched is reached.

List sorted in ascending order

1 5 7 8 9 12 15

Search for 10 in the above list

We reached 12. Since 12>10 Searching stops.

Search for 9. When 9 will be found the search stops.

List sorted in descending order

15 12 11 9 6 4

Search for 10. We reached 9. 9<10. Searching stops

Searching in case of unsorted list starts from the 0th element and continues until the element is found or the end of list is reached.

Performance of Linear search algorithm can be measured by counting the comparisons done to find out an element. The number of comparisons is O(n).

Advertisements