Search algorithms

Notes on search algorithms.

Linear Search

This is the most naive search algorithm. In an array, start comparing the search key with the left most element and keep moving the index one by one till the end. Time complexity – O(n), n being the size of the array.

 for(int i = 0; i < n; i++){
            if(array[i] == searchKey){
                System.out.println("Key found");
                return;
            }
        }

Binary Search

This is based on the concept of binary search tree. We could apply the logic on the array without constructing the tree. This works on the sorted array. Take the middle element of the array, compare it with the search key; If the key is smaller, take the middle element of the left segment and compare. Repeat the same process till the key is found or the number of elements in the segment becomes one. Time complexity – O(log n). This is one of the most popular search algorithm.

Interpolation Search

This is an improvement over binary search. It also works in sorted array. Binary search always take the middle element of the sub-array and compare. Interpolation search has a mechanism called problem which attempts to make an educated guess of the index closer to the search key based on the values in the ends of the sub-array. Find a sample here.

Trie based search

It’s suitable for string search over a set of strings. Good example for this is address book search in phones.  Learn more about Trie.