Algorithms

Various Algorithms in Problem Solving Logic to reduce time complexity are discussed here

Searching Algorithms

There are two types of Basic Algorithm in Programming. they are:

  1. Searching Algorithm
  2. Sorting Algorithm

click here to learn about sorting algorithms

  1. Searching is the process of finding some particular element in the list.
  2. If the element is present in the list, then the process is called successful and the process returns the location of that element, otherwise the search is called unsuccessful.
  3. There are two popular search methods that are widely used in order to search some item into the list.

Linear Search

Binary Search

LINEAR SEARCH

In this type of searching, we simply traverse the list completely and match each element of the list with the item whose location is to be found. If the match found then location of the item is returned otherwise the algorithm return NULL.

Algorithm :

LINEAR_SEARCH(A, N, VAL)

  • Step 1: [INITIALIZE] SET POS = -1
  • Step 2: [INITIALIZE] SET I = 1
  • Step 3: Repeat Step 4 while I<=N
  • Step 4: IF A[I] = VAL

SET POS = I

PRINT POS

Go to Step 6

[END OF IF]

SET I = I + 1

[END OF LOOP]

  • Step 5: IF POS = -1

PRINT " VALUE IS NOT PRESENTIN THE ARRAY "

[END OF IF]

  • Step 6: EXIT
Linear Search Implementation:

import java.util.Scanner;  
public class Main
{  
public static void main(String[] args)
{  
    Scanner sc=new Scanner(System.in);
    int n=sc.nextInt();
    int[] arr=new int[n];
    for(int index=0;index<n;index++)
    {
        arr[index]=sc.nextInt();
    }
    int item,flag=0;   
    item = sc.nextInt();  
    for(int i = 0; i<10; i++)  
    {  
        if(arr[i]==item)  
        {  
            flag = i+1;  
            break;  
        }  
        else   
            flag = 0;   
    }  
    if(flag != 0)  
    {  
        System.out.println("Item found at location " + flag);  
    }  
    else   
        System.out.println("Item not found");  
}  
}

input 1:
11
10 23 15 8 4 3 25 30 34 2 19
25

output 1:
Item found at location 7

input 2:
11
10 23 15 8 4 3 25 30 34 2 19
12

output 2:
Item not found

BINARY SEARCH

Binary search is the search technique which works efficiently on the sorted lists.

Binary search follows divide and conquer approach in which, the list is divided into two halves and the item is compared with the middle element of the list.

If the match is found then, the location of middle element is returned otherwise, we search into either of the halves depending upon the result produced through the match.

ALGORITHM:

  • Step 1: [INITIALIZE] SET BEG = lower_bound

END = upper_bound, POS = - 1

  • Step 2: Repeat Steps 3 and 4 while BEG <=END
  • Step 3: SET MID = (BEG + END)/2
  • Step 4: IF A[MID] = VAL

SET POS = MID

PRINT POS

Go to Step 6

ELSE IF A[MID] > VAL

SET END = MID - 1

ELSE

SET BEG = MID + 1

[END OF IF]

[END OF LOOP]

  • Step 5: IF POS = -1

PRINT "VALUE IS NOT PRESENT IN THE ARRAY"

[END OF IF]

  • Step 6: EXIT

Let us consider an array arr = {1, 5, 7, 8, 13, 19, 20, 23, 29}. Find the location of the item 23 in the array. 

Binary Search Implementation:

import java.util.*;  
public class Main
{
    static int binarySearch(int[] a, int beg, int end, int item)  
   {  
    int mid;  
    if(end >= beg)   
    {     
        mid = (beg + end)/2;  
        if(a[mid] == item)  
        {  
            return mid+1;  
        }  
        else if(a[mid] < item)   
        {  
            return binarySearch(a,mid+1,end,item);  
        }  
        else   
        {  
            return binarySearch(a,beg,mid-1,item);  
        }  
      
    }  
    return -1;   
} 
public static void main(String[] args) 
{
    Scanner sc=new Scanner(System.in);
    int n=sc.nextInt();
    int[] arr=new int[n];
    for(int index=0;index<n;index++)
    {
        arr[index]=sc.nextInt();
    }
    int item, location = -1;   
    item = sc.nextInt();  
    location = binarySearch(arr,0,n-1,item);  
    if(location != -1)  
    System.out.println("The location of the item is "+location);  
    else   
        System.out.println("Item not found");  
    }  
}  

input 1:
10
16 19 20 23 45 56 78 90 96 100
23

output 1:
The location of the item is 4

input 2:
10
16 19 20 23 45 56 78 90 96 100
54

output 2:
Item not found

JUMP SEARCH

  1. Jump Search is a searching algorithm for sorted arrays.
  2. The basic idea is to check fewer elements (than linear search) by jumping ahead by fixed steps or skipping some elements in place of searching all elements.

Let’s consider the following array: (0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610). Length of the array is 16. Jump search will find the value of 55 with the following steps assuming that the block size to be jumped is 4.

STEP 1: Jump from index 0 to index 4;

STEP 2: Jump from index 4 to index 8;

STEP 3: Jump from index 8 to index 12;

STEP 4: Since the element at index 12 is greater than 55 we will jump back a step to come to index 8.

STEP 5: Perform linear search from index 8 to get the element 55.


Note:

In the worst case, we have to do n/m jumps and if the last checked value is greater than the element to be searched for, we perform m-1 comparisons more for linear search. Therefore the total number of comparisons in the worst case will be ((n/m) + m-1). The value of the function ((n/m) + m-1) will be minimum when m = √n. Therefore, the best step size is m = √n. 

Jump search Implementation

import java.util.*;
public class Main
{ 
    static int jumpSearch(int[] arr, int x) 
    { 
        int n = arr.length; 
        int step = (int)Math.floor(Math.sqrt(n)); 
        int prev = 0; 
        while (arr[Math.min(step, n)-1] < x) 
        { 
            prev = step; 
            step += (int)Math.floor(Math.sqrt(n)); 
            if (prev >= n) 
                return -1; 
        } 
        while (arr[prev] < x) 
        { 
            prev++; 
            if (prev == Math.min(step, n)) 
                return -1; 
        } 
        if (arr[prev] == x) 
            return prev; 
        return -1; 
    } 
    public static void main(String [ ] args) 
    { 
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] arr=new int[n];
        for(int index=0;index<n;index++)
        {
            arr[index]=sc.nextInt();
        }
        int item=sc.nextInt(); 
        int index1 = jumpSearch(arr, item); 
        System.out.println("Number " + item + " is at index " + index1); 
    } 
}

input 1:
16
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610
55

output 1:
Number 55 is at index 10

INTERPOLATION SEARCH

The Interpolation Search is an improvement over Binary Search for instances, where the values in a sorted array are uniformly distributed.

Binary Search always goes to the middle element to check. On the other hand, interpolation search may go to different locations according to the value of the key being searched.

To find the position to be searched, it uses following formula.

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

arr[] ==> Array where elements need to be searched
x     ==> Element to be searched
lo    ==> Starting index in arr[]
hi    ==> Ending index in arr[]

Algorithm :

Step1: In a loop, calculate the value of “pos” using the probe position formula.

Step2: If it is a match, return the index of the item, and exit.

Step3: If the item is less than arr[pos], calculate the probe position of the left sub-array. Otherwise calculate the same in the right sub-array.

Step4: Repeat until a match is found or the sub-array reduces to zero.

Interpolation Search implementation:

import java.util.*;
public class Main
{
    static int interpolationSearch(int[] arr,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+1;
            if (arr[pos] < x) 
                lo = pos + 1; 
            else
                hi = pos - 1; 
        } 
        return -1; 
    } 
    public static void main(String[] args)  
    { 
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] arr=new int[n];
        for(int index=0;index<n;index++)
        {
            arr[index]=sc.nextInt();
        }
         int item= sc.nextInt();
         int index1 = interpolationSearch(arr,item); 
         if (index1 != -1) 
               System.out.println("Element found at position " + index1); 
            else
               System.out.println("Element not found."); 
    } 
} 

input 1:
15
10 12 13 16 18 19 20 21 22 23 24 33 35 42 47
18

output 1:
Element found at position 5

input 2:
15
10 12 13 16 18 19 20 21 22 23 24 33 35 42 47
39

output 2:
Element not found.

TERNARY SEARCH

It is a divide and conquer algorithm that can be used to find an element in an array.

In this, we divide the given array into three parts and determine which has the key (searched element).

We can divide the array into three parts by taking mid1 and mid2 which can be calculated as shown below. Initially, l and r will be equal to 0 and n-1 respectively, where n is the length of the array.

mid1 = l + (r-l)/3

mid2 = r – (r-l)/3

STEPS:

  1. First, we compare the key with the element at mid1. If found equal, we return mid1.
  2. If not, then we compare the key with the element at mid2. If found equal, we return mid2.
  3. If not, then we check whether the key is less than the element at mid1. If yes, then recur to the first part.
  4. If not, then we check whether the key is greater than the element at mid2. If yes, then recur to the third part.
  5. If not, then we recur to the second (middle) part.
Recursive Implementation of Ternary Search:

import java.util.*;
public class Main
{ 
    static int ternarySearch(int l, int r, int key, int ar[]) 
    { 
        if (r >= l) 
        { 
            int mid1 = l + (r - l) / 3; 
            int mid2 = r - (r - l) / 3; 
            if (ar[mid1] == key) 
            { 
                return mid1; 
            } 
            if (ar[mid2] == key)
            { 
                return mid2; 
            } 
            if (key < ar[mid1])
            { 
                return ternarySearch(l, mid1 - 1, key, ar); 
            } 
            else if (key > ar[mid2]) 
            {
                return ternarySearch(mid2 + 1, r, key, ar); 
            } 
            else 
            { 
                return ternarySearch(mid1 + 1, mid2 - 1, key, ar); 
            } 
        } 
        return -1; 
    } 
    public static void main(String args[]) 
    { 
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] arr=new int[n];
        for(int index=0;index<n;index++)
        {
            arr[index]=sc.nextInt();
        }
        int key = sc.nextInt();
        int p = ternarySearch(0, n-1, key, arr); 
        System.out.println("Index of " + key + " is " + p); 
    } 
} 

input 1:
10
1 2 3 4 5 6 7 8 9 10
6

output 1:
Index of 6 is 5

EXPONENTIAL SEARCH

It works in O(Log n) time.

It starts with subarray size 1, compare its last element with x, then try size 2, then 4 and so on until last element of a subarray is not greater.

Once we find an index i (after repeated doubling of i), we know that the element must be present between i/2 and i (Why i/2? because we could not find a greater value in previous iteration) 

Implementation of Exponential Search:

import java.util.*; 
public class Main
{ 
    static int exponentialSearch(int arr[],int n, int x) 
    { 
        if (arr[0] == x) 
            return 0; 
        int i = 1; 
        while (i < n && arr[i] <= x) 
            i = i*2; 
        return Arrays.binarySearch(arr, i/2,Math.min(i, n), x); 
    } 
    public static void main(String args[]) 
    { 
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] arr=new int[n];
        for(int index=0;index<n;index++)
        {
            arr[index]=sc.nextInt();
        }
        int item = sc.nextInt(); 
        int result = exponentialSearch(arr, n, item); 
        System.out.println((result < 0) ? "Element is not present in array" : "Element is present at index " +  result); 
    } 
}

input 1:
5
2 3 5 10 50
10

output 1:
Element is present at index 4

SUBLIST SEARCH

Used to check whether the first list is present in 2nd list or not

Algorithm:

1- Take first node of second list.

2- Start matching the first list from this first node.

3- If whole lists match return true.

4- Else break and take first list to the first node again.

5- And take second list to its second node.

6- Repeat these steps until any of linked lists becomes empty.

7- If first list becomes empty then list found else not. 

SubList Search implementation using LinkedList

import java.util.*; 
public class Main  
{  
static class Node  
{ 
    int data; 
    Node next; 
}; 
static boolean findList(Node first, 
                        Node second) 
{ 
    Node ptr1 = first, ptr2 = second; 
    if (first == null && second == null) 
        return true; 
    if (first == null || 
       (first != null && second == null)) 
        return false; 
    while (second != null) 
    { 
        ptr2 = second; 
        while (ptr1 != null) 
        { 
            if (ptr2 == null) 
                return false;
            else if (ptr1.data == ptr2.data) 
            { 
                ptr1 = ptr1.next; 
                ptr2 = ptr2.next; 
            } 
            else break; 
        } 
        if (ptr1 == null) 
            return true; 
        ptr1 = first; 
        second = second.next; 
    } 
    return false; 
}
static void printList(Node node) 
{ 
    while (node != null) 
    { 
        System.out.printf("%d ", node.data); 
        node = node.next; 
    } 
} 
static Node newNode(int key) 
{ 
    Node temp = new Node(); 
    temp.data= key; 
    temp.next = null; 
    return temp; 
} 
public static void main(String[] args)  
{ 
    Node a = newNode(1); 
    a.next = newNode(2); 
    a.next.next = newNode(3); 
    a.next.next.next = newNode(4); 
  
    Node b = newNode(1); 
    b.next = newNode(2); 
    b.next.next = newNode(1); 
    b.next.next.next = newNode(2); 
    b.next.next.next.next = newNode(3); 
    b.next.next.next.next.next = newNode(4); 
  
    if(findList(a, b) == true)  
        System.out.println("LIST FOUND"); 
    else
        System.out.println("LIST NOT FOUND"); 
} 
} 

Input 1: list1 =  10->20
         list2  = 5->10->20
Output 1: LIST FOUND

Input  2: list1 =  1->2->3->4
         list2  = 1->2->1->2->3->4
Output 2: LIST FOUND

Input  3: list1 =  1->2->3->4
         list2  = 1->2->2->1->2->3
Output 3: LIST NOT FOUND

FIBONACCI SEARCH

Fibonacci Numbers are recursively defined as F(n) = F(n-1) + F(n-2), F(0) = 0, F(1) = 1. First few Fibinacci Numbers are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

Algorithm:

Let the searched element be x.

The idea is to first find the smallest Fibonacci number that is greater than or equal to the length of given array. Let the found Fibonacci number be fib (m’th Fibonacci number). We use (m-2)’th Fibonacci number as the index (If it is a valid index). Let (m-2)’th Fibonacci Number be i, we compare arr[i] with x, if x is same, we return i. Else if x is greater, we recur for subarray after i, else we recur for subarray before i.

Below is the complete algorithm

Let arr[0..n-1] be the input array and element to be searched be x.

  1. Find the smallest Fibonacci Number greater than or equal to n. Let this number be fibM [m’th Fibonacci Number]. Let the two Fibonacci numbers preceding it be fibMm1 [(m-1)’th Fibonacci Number] and fibMm2 [(m-2)’th Fibonacci Number].
  2. While the array has elements to be inspected:
    1. Compare x with the last element of the range covered by fibMm2
    2. If x matches, return index
    3. Else If x is less than the element, move the three Fibonacci variables two Fibonacci down, indicating elimination of approximately rear two-third of the remaining array.
    4. Else x is greater than the element, move the three Fibonacci variables one Fibonacci down. Reset offset to index. Together these indicate elimination of approximately front one-third of the remaining array.
  3. Since there might be a single element remaining for comparison, check if fibMm1 is 1. If Yes, compare x with that remaining element. If match, return index.
Fibonacci Search Implementation:

import java.util.*; 
public class Main
{    
    public static int min(int x, int y)  
    { 
        return (x <= y)? x : y; 
    } 
    public static int fibMonaccianSearch(int arr[],int x, int n) 
    { 
        int fibMMm2 = 0;  
        int fibMMm1 = 1; 
        int fibM = fibMMm2 + fibMMm1;
        while (fibM < n) 
        { 
            fibMMm2 = fibMMm1; 
            fibMMm1 = fibM; 
            fibM = fibMMm2 + fibMMm1; 
        } 
        int offset = -1; 
        while (fibM > 1) 
        { 
            int i = min(offset+fibMMm2, n-1); 
            if (arr[i] < x) 
            { 
                fibM = fibMMm1; 
                fibMMm1 = fibMMm2; 
                fibMMm2 = fibM - fibMMm1; 
                offset = i; 
            }
            else if (arr[i] > x) 
            { 
                fibM = fibMMm2; 
                fibMMm1 = fibMMm1 - fibMMm2; 
                fibMMm2 = fibM - fibMMm1; 
            } 
            else return i; 
        } 
        if(fibMMm1 == 1 && arr[offset+1] == x) 
            return offset+1; 
        return -1; 
    } 
    public static void main(String[] args) 
    { 
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] arr=new int[n];
        for(int index=0;index<n;index++)
        {
            arr[index]=sc.nextInt();
        }
        int x = sc.nextInt(); 
        System.out.print ("Found at index: "+fibMonaccianSearch(arr, x, n)); 
    } 
} 

input 1:
11
10 22 35 40 45 50 80 82 85 90 100
85

output 1:
Found at index: 8

UBIQUITOUS BINARY SEARCH

Given a sorted array of N distinct elements. Find a key in the array using least number of comparisons. (least number of comparisons)

Here are some different logic for this case:(consider a sample program)

LOGIC 1:

import java.util.*; 
public class Main
{    
    static int BinarySearch(int A[], int l, int r, int key) 
{ 
    int m; 
  
    while( r - l > 1 ) 
    { 
        m = l + (r-l)/2; 
  
        if( A[m] <= key ) 
            l = m; 
        else
            r = m; 
    } 
  
    if( A[l] == key ) 
        return l; 
   else if( A[r] == key ) 
        return r; 
    else
        return -1; 
} 
    public static void main(String[] args) 
    { 
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] arr=new int[n];
        for(int index=0;index<n;index++)
        {
            arr[index]=sc.nextInt();
        }
        int x = sc.nextInt(); 
        System.out.print ("Found at index: "+BinarySearch(arr, 0, n-1,x)); 
    } 
} 

input 1:
11
10 22 35 40 45 50 80 82 85 90 100
85

output 1:
Found at index: 8

input 2:
11
10 22 35 40 45 50 80 82 85 90 100
22

output 2:
Found at index: 1

LOGIC 2:

int BinarySearch(int A[], int l, int r, int key) 
{ 
   int m; 
    while( r - l > 1 ) 
    { 
        m = l + (r-l)/2; 
        if( A[m] <= key ) 
            l = m; 
        else
            r = m; 
    } 
    if( A[l] == key ) 
        return l; 
   else if( A[r] == key ) 
        return r; 
    else
        return -1; 
}

LOGIC 3:

int Floor(int A[], int l, int r, int key) 
{ 
    int m; 
    while( r - l > 1 ) 
    { 
        m = l + (r - l)/2; 
        if( A[m] <= key ) 
            l = m; 
        else
            r = m; 
    } 
    return A[l]; 
} 
int Floor(int A[], int size, int key) 
{ 
    if( key < A[0] ) 
        return -1; 
    return Floor(A, 0, size, key); 
}

LOGIC 4:

int GetRightPosition(int A[], int l, int r, int key) 
{ 
    int m; 
    while( r - l > 1 ) 
    { 
        m = l + (r - l)/2; 
        if( A[m] <= key ) 
            l = m; 
        else
            r = m; 
    } 
    return l; 
} 
int GetLeftPosition(int A[], int l, int r, int key) 
{ 
    int m; 
    while( r - l > 1 ) 
    { 
        m = l + (r - l)/2; 
        if( A[m] >= key ) 
            r = m; 
        else
            l = m; 
    } 
    return r; 
} 
int CountOccurances(int A[], int size, int key) 
{  
    int left = GetLeftPosition(A, -1, size-1, key); 
    int right = GetRightPosition(A, 0, size, key);  
    return (A[left] == key && key == A[right])?(right - left + 1) : 0; 
}

LOGIC 5:

int BinarySearchIndexOfMinimumRotatedArray(int A[], int l, int r) 
{  
    int m;  
    if( A[l] <= A[r] ) 
        return l; 
    while( l <= r ) 
    {  
        if( l == r ) 
            return l; 
        m = l + (r-l)/2;  
        if( A[m] < A[r] ) 
            r = m; 
        else
            l = m+1; 
    } 
  
    return -1; 
} 
int BinarySearchIndexOfMinimumRotatedArray(int A[], int size) 
{ 
    return BinarySearchIndexOfMinimumRotatedArray(A, 0, size-1); 
}

META BINARY SEARCH (One sided Search)