Searching different types for Data Structure

March 19, 2014 0 Comments

We study here different types of searching like linear search and binary search applied on linear data structure, lists (array and linked list).

Linear search:
In this type search each and every element of the data structure (array or linked list) is compared with the key element till either the element is found or the list is over. The linear searching technique is used when there is no availability of direct address of the elements. Even though the address of the element is directly available, the application of linear search also depends on the order of elements stored in a list. So linear search can be applied either to one-dimensional array where the elements are not necessarily arranged in any order (although the address of any element is available directly) or to linked list where the address of any element is directly not available (although the elements may be ordered).
Binary search:
    In this type of search the elements in the list must be arranged in an order and the address of any element must be available directly. The direct availability of any element ’s address is only possible in case of one dimensional array can be arranged in order. So the binary search can only be applied to one dimensional array. In case of linked list binary search can not be applied because, even the elements may be arranged in an order, but the address of any element is not available directly.

Linear search applied to one dimensional array:
           Understanding and implementation of linear search to single or one dimensional array is simple. In any one-dimensional array the key to be searched is simply compared with all the elements of the array one by one till the last element. In between if the search is successful means if the key is equal to one of the elements then stop the comparison and return success. When comparison of the key with all the elements is over then return non-success. Usually when searching is applied to the list we assume that the elements are unique. So to apply linear search the elements of the array may not necessarily be in ascending or descending order. Remember that even though every element’s address is directly available, the linear search always performs comparison of key with the first element only and runs till the last element.

Jackrin Reacher

Some say he’s half man half fish, others say he’s more of a seventy/thirty split. Either way he’s a fishy bastard. Google