Sequential, Binary and Tree Search

Search algorithms are mainly implemented as :

1. Sequential Search
2. Binary Search
3. Tree Search

Sequential Search:

A sequential search is the simplest form of search. There's no need for sorted data in this type of search. It is applicable to a table organized either as an array or as a linked list. It checks every element, one at a time and in sequence, until the desired one is found.This method is relatively slower compared to other searching methods if the list has more elements.

Algorithm for sequential search:

for (i= 0; i< n; i++)
if (key == k(i))
return (i);
return (-1);

* where key is the search argument.

Working Method:

• First of all it checks the key with array first element ie. arr[0], then checks to arr[1], arr[2],…….arr[n-1]. As shown in figure
• If it finds the key during the process, it returns the index of the key. Otherwise, it returns -1 (or failure)
  • For example: In the above array, if we have to search 17, we start from 54 to 26, to 93 and then stop at 17, returning 3 (the index of 17).

Example:

Find 3 in the following unsorted data:

return 3

Efficiency of Sequential Search

To find the required data from the record , at most “n” comparisons is necessary.
Thus, The complexity is O(n).

Indexed Sequential Search

• It is the technique to improve search efficiency for a sorted file
• Requires additional space than that of Sequential Search
• It does not search through the array directly. But searches to the index instead. As it finds the relative array in the index then only it goes to that array place and searches through an array.

Binary Search

Let us consider an array of elements. We need to search an element. If the array contains only one element, we compare the required element with the one and determine if its present; else compare the item being searched for with the item at the middle of the array. If they are equal, the search has been completed successfully. If the middle element is greater than the item being searched for, the search process is repeated in the first half of the array; otherwise ,the process is repeated in the second half.

Note that each time a comparison is made , the number of elements yet to be searched is cut in half. For large arrays, this method is superior to sequential search in which each comparison reduces the number of elements yet to search by only one. Because of the division of the array to be searched into two parts , this search method is called the binary search.

Visualization of the binary search algorithm where 4 is the target value.

Binary search is the most efficient method of searching sequential table without the use of auxiliary indices or tables.The argument is compared with a key of middle element of a table. If they are equal, the search terminates.Otherwise, either upper half or lower half of table is searched.It works with the recursive algorithm.

Algorithm

We now present a recursive algorithm to search a sorted array A for an element x between A[low] and A[high].The algorithm returns an index of A for an element equals x if such an index exists between low and high. If x is not found in that portion of the array, binsrch returns -1.

1. if(low>high)
2. return -1;
3. mid = (low + high)/2;
4. if(x == A[mid])
5. return mid;
6. if( x < a[mid])
7. search for x in A[low] to A[mid - 1];
8. else
9. search for x in A[mid + 1] to A[high];

• A search on one element is not defined directly as the appropriate index. Instead, that element is compared with the item being searched for. If the two items are not equal, the search continues in the first or second half; each of which contains no element. This case is indicated by the condition low > high, and its result is defined directly as -1.

Analysis:

Data structureWorst case performanceBest case performanceAverage case performance

Tree Search

Tree searching is used for searching a specific information from a record arranged in the form of binary search tree.

Search Operation

• Searching in BST is recursive or iterative.
• Begin by examining the root note.
• If the key is less than the root, search the left sub tree.
• If it is greater than the root, search the right sub tree.
• Repeat until the key is found or the remaining sub tree is null.
• If the searched key is not found before a null sub tree is reached, then the item must not be present in the tree.

Algorithm:

algorithm Find(key, root):
current-node := root
while current-node is not Null do
if current-node.key = key then
return current-node
else if key < current-node.key then
current-node := current-node.left
else
current-node := current-node.right

References:

1.https://en.wikipedia.org/wiki/Search_algorithm

2.https://en.wikipedia.org/wiki/Binary_search_algorithm

3.https://en.wikipedia.org/wiki/Tree_traversal

4. Karumanchi, N. "Data Structures and Algorithms Made Easy"