Searching data

Searching is the other problem that often occurs when handling data. The search can be done with some part of the actual data called a key. The easiest way to search is the linear search: successive elements are examined until either the item is found or the end of the list is reached. This is however an extremely inefficient way to search because in average about n/2 elements must be searched and in the worst case the element is not found but all n elements have been searched any way. A more efficient way to search is to first sort the elements. Searching is then faster because it is known that the item is missing when the correct place in the array is passed.

A rather simple but efficient searching algorithm is called binary search. The elements must be in ascending or descending order.

Algorithm: Binary search
    left <--- 0
    right <--- element_amount - 1
    WHILE left <= right
        middle <--- ( left + right )/2
        IF elements[ middle ].key == searched_key THEN
           item found at location middle
        ELSE IF elements[ middle ].key < searched_key THEN
           left <--- middle + 1
        ELSE
           right <--- middle - 1
    item not in the array

How does the binary search work with an integer key:
The search key is 4, there are 10 elements with the key 0-10 in the array



Fig: Binary search mechanism


Note that Binary Search can be used to work with other types than string by changing some points in the code to match the type. string must be changed to match the type of the searched data. The comparisons in the algorithms need to compare the wanted type.

Reference: allexperts, onesmartclick, informit

Previous post

Next post