Searching Algorithms Concepts

Searching Algorithms

In Computer Science, a search algorithm is any algorithm which solves the search problem, namely, to retrieve information stored within some data structure, or calculated in the search spaceo of a problem domain, either with discrete or continuous values. Specific applications of search algorithms include: Routing, Sudoku puzzle solvers, Hash maps, search trees.

There are the types of Searching algorithms we will cover:

Linear Search Algorithms
Binary Search Algorithms
Interpolation Search Algorithm
Hash Tables

Linear Search Algorithms

A Linear search scans one item at a time, without jumping to any item. It sequentially checks each element of the list until a match is found or the whole list has been searched. The objective is to find an element within a list.

An Example of how a linear search algorithm works in Java:


                            class findMyItem{
    
    public static int search(int arr[]; int x){

        int n = arr.length;
        for(int i=0; i<n; i++){

            if(arr[i] == x){

                return i;

            }
            return -1;

        }

    }

    public static void main(String args[]){

        int arr[] = {2,3,4,10,40};
        int x = 10;

        int result = search(arr,x);

        if(result == -1){

            System.out.println("Element is not present in array");

        } else {

            System.out.println("Element is present at index " + result);

        }

    }

}

// output:

// Element is present at index 3

The process above can be shown in steps here:


                            array = [4,20,5,70,23,4,6,10];

Let's say we want to find 23:

You basically just check every index starting from 0

Index No:
----------

0 = 4 keep going
1 = 20 keep going
2 = 5 keep going
3 = 70 keep going
4 = 23 stop and end program

A linear search is effectively starting from the leftmost element of the array and one by one comparing x with each element in that array, if x matches with an element then it will return the index. If x doesn't match with any of the elements, then it returns -1.

Linear Search algorithms in this sort of context are the most basic searching algorithms, you may have come across them already and they are useful when searching in small arrays.

Binary Search Algorithms

Binary Search Algorithms work on sorted arrays. They are target a value in a sorted array by finding the position.

An Example of how a Binary Search Algorithm works in Java - Here is the given code:


                            class BinarySearch{
    // Returns index of x if it is present in arr[]
    // else return -1
    
    int binarySearch(int arr[], int x){

        int l=0; r=arr.length-1;
        while(l<=r){

            int m = l + (r - l) / 2;

            // Check if x is present at mid
            if(arr[m] == x){

                return m;

            }

            // If x greater, ignore left half
            if(arr[m] < x){

                l = m + 1;

            // If x is smaller, ignore right half
            } else {

                r = m - 1;

            }

        }

        // If we reach here, then element was
        // not present

        return -1;

    }

    public static void main(String args[]){

        BinarySearch ob = new BinarySearch();
        int arr[] = {2,3,4,10,40};
        int n = arr.length;
        int x = 10;
        int reault = ob.binarySearch(arr,x);

        if(result == -1){

            System.out.println("Element not present");

        } else {

            System.out.println("Element found at index " + result);

        }

    }

}

// Output:
// Element present at index 3

This can be shown as:


                            Array: [3,6,10,14,20,25,26,30];

Search 25:

Left = 0, Right = 7;

M = Left + (Right-Left)/2 = 3;

Index 3 is 14
25 is bigger than 14 so we ignore left half and focus on right half

Left = M + 1;

So now Left is 4 and we do it all over again:

Left = 4, Right = 7

M = 4 + (7-4)/2 = 5.5 => 5;

Index 5 is 25

Return 25 :)

The Binary Search is performed by repeatedly dividing the search interval in half. Begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise narrow it to the upper half. Repeatedly check until the value is found or the interval is empty. The array must be sorted before searching.

Binary Searches are really good for medium sized arrays and are a lot quicker than Linear Search arrays, only difference is that your array has to be sorted before you do the search.

Interpolation Search

Interpolation Search is an improved variant of binary search. This search algorithm works on the probing position of the required value. For this algorithm to work properly, the data collection should be in a sorted form and equally distributed.

An Example of how Interpolation Search works in Java:


                            class InterpolationSearch{
    
    static int arr[] = new int[]{10,12,13,16,18,19,20,21,22,23,24,33,35,42,47};

    static int interpolationSearch(int x){

        int lo = 0, hi = (arr.length-1);

        while(lo < hi && x >= arr[lo] && x <= arr[hi]){

            if(lo == hi){

                if(arr[lo] == x){

                    return lo;

                }

                return -1;
            
            }

            int pos = lo + (((hi-lo) / (arr[hi]-arr[lo])) * (x - arr[lo]));

            if(arr[pos] == x){

                return pos;

            }

            if(arr[pos] < x){

                lo = pos + 1;

            } else {

                hi = pos - 1;

            }

        }

        return -1;

    }

    public static void main(String[] args){

        int x = 18; // Element to be searched
        int index = interpolationSearch(x);

        //If element was found

        if(index != -1){

            System.out.println("Element found at index " + index);

        } else {

            System.out.println("Element not found");

        }

    }

}

// Output:

Element found at index 4

This can be shown as:


                            We can simplify this out into steps:

Step 1: Start searching data from middle of the list.
Step 2: If it is a match, return the index of the item, and exit.
Step 3: If it is not a match, probe position.
Step 4: Divide the list using probing formula and find the new middle.
Step 5: If data is greater than middle, search in higher sub-list.
Step 6: If data is smaller than middle, search in lower sub-list.
Step 7: Repeat until match.

The Probing Formula:

mid = Lo + ((Hi - Lo) / (A[Hi] - A[Lo])) * (X - A[Lo])

where - 
A = list
Lo = Lowest Index of the list
Hi = Highest Index of the list
A[n] = Value stored at Index n in the list

Array: [4,7,11,14,15,20,24,28,30,32,35]

Array Length = 11

Search: 11

Left = 0, Right = 11;

M = Left + (Right-Left)/2 = 5

Index 5 is 20 - false

M = Left + ((Right - Left) / (Array[Right] - Array[Left])) * (X - Array[Left])
M = 2.48 = 2

Index of 2 is 11 - true!

As you can see, Interpolation search is faster and quicker than Binary Search. Its essentially an add on.

Just as with Binary Search, Interpolation Search needs to have a sorted array to search from.

Hash Tables

A hash table is a data structure that implements an associative array abstract data type, a structure that can map keys to values. A hash table uses a hash function to compute an index into an array of buckets or slots. Hashing is a technique to convert a range of key values into a range of indexes of an array.

An Example of how Hash Table Searches work in Java:


                            import java.io.*;
import java.util.HashSet;

public class HashSetDemo{
    
    public static void main(String args[]){

        HashSet<String> set = new HashSet<String>();

        set.add("Hi");
        set.add("My");
        set.add("Name");
        set.add("Is");
        set.add("Jay");

        System.out.println("HashSet: " + set);

        System.out.println("Does the Set contain 'Jay'? " + set.contains("Jay"));

        System.out.println("Does the set contain 'SoloLearn'? " + set.contains("SoloLearn"));

    }

}

// Output:

HashSet: [Hi,Is,Jay,My,Name]
Does the Set contain 'Jay'? true
Does the set contain 'SoloLearn'? false

This can be shown as:


                            HashSet:

Index | Value
--------------
0     | Hi 
1     | Is
2     | Jay
3     | My
4     | Name

The set contains Jay and the set does not contain SoloLearn

We created a HashSet for a set of String data types. We have then sorted these types in a set. The 'contains()' method allows us to search for value. Hash Tables are very quick as the data has already been sorted into buckets. There will be more on Hash Tables in the future (about how they work etc).

Hash Table elements are unique from each other, even if they were the same value, they would still have a unique index. The operations performed on this data structure are very fast and most people usually use Hash Tables / Sets when searching for data.

These are the different types of Searching Algorithms. There will be more Searching Algorithms covered in the future, such as Search Trees (breatdh first and depth first etc) and Jump Search.

Searching Algorithm Concepts