Every THING is Internet of Thing

Search Algorithms

 
  • Akhilesh Moghe
  • Dec 14, 2018

Search Algorithms

  • Linear Search is very Rarely used.
  • Time Complexity is O(n).
/*
Time Complexity is O(n).
Linear Search is very Rarely used.
*/
#include <iostream>
using namespace std;
// C++ code for linearly search x in arr[]. If x
// is present then return its location, otherwise
// return -1
int search(int arr[], int n, int x)
{
int i;
for (i = 0; i < n; i++)
if (arr[i] == x)
return i;
return -1;
}
int main()
{
int arr[6] = {20, 57, 23, 45, 12, 76};
int index = search(arr, 6, 6);
cout << "76 is at index " << index << endl;
return 0;
}
view raw Linear_Search.cpp hosted with ❤ by GitHub
  • Binary Search needs SORTED array.
  • Time Complexity is O(Log n).
  • Binary Search Logic:
    • 1st Compare x with Middle element, if matched return.
    • if x is greater than Middle element, search in right half of array.
    • if x is smaller than Middle element, search in left half of array.
  • Iterative Vs Recursive:
    • Both approaches will have the same time complexity “O(log(n))”, but they will different in term of space usage.
    • :x:    Recursive May reach to log(n) space (because of the stack),
    • :heavy_check_mark:    Iterative BS should be done in O(1) space complexity.
/*
Binary Search needs SORTED array.
Time Complexity is O(Log n).
Binary Search Logic:
* 1st Compare x with Middle element, if matched return
* if x is greater than Middle element, search in right half of array
* if x is smaller than Middle element, search in left half of array
Iterative Vs Recursive:
Both will have the same time complexity “O(log(n))”, but they will different in term of space usage.
Recursive May reach to log(n) space (because of the stack),
Iterative BS should be done in O(1) space complexity.
*/
#include <iostream>
using namespace std;
// C++ code for linearly search x in arr[]. If x
// is present then return its location, otherwise
// return -1
// 12 20 23 45 57 76
int BinarySearchRecursive(int arr[], int left, int right, int x)
{
if(right >= left)
{
int midIndex = left + (right-left)/2;
if(arr[midIndex] == x)
return midIndex;
if(arr[midIndex] > x)
return BinarySearchRecursive(arr, left, midIndex-1, x);
else
return BinarySearchRecursive(arr, midIndex+1, right, x);
}
return -1;
}
int BinarySearchIterative(int arr[], int left, int right, int x)
{
while(left <= right)
{
int midIndex = left + (right-left)/2;
if(arr[midIndex] == x)
return midIndex;
// if x is greater than midIndex value, search in right half of array
if(arr[midIndex] < x)
left = midIndex + 1;
// if x is less than midIndex value, search in left half of array
else
right = midIndex - 1;
}
return -1;
}
int main()
{
// Array needs to be Sorted
int arr[6] = {12, 20, 23, 45, 57, 76};
int arrLength = sizeof(arr)/sizeof(int);
int index = BinarySearchRecursive(arr, 0, (arrLength-1), 45);
cout << "76 is at index " << index << endl;
index = BinarySearchIterative(arr, 0, (arrLength-1), 45);
cout << "76 is at index " << index << endl;
return 0;
}
view raw Binary_Search.cpp hosted with ❤ by GitHub
  • Jump Search Algorithm is for SORTED arrays.
  • This Algorithm check ‘fewer elements’ (than linear search) by jumping ahead by fixed steps or skipping some elements.
  • Time Complexity is O(Sqrt(n)).

  • Algorithm:

    1)    arr[],
    2)    n = size,
    3)    m = Steps to Jump,
    4)    x = element to find,
    5)    Search for indexex = arr[0], arr[m], arr[2m], … , arr[km]
    6)    Find an interval as:
               arr[km] < x < arr[(k+1)m]
    7)    Perform ‘Linear Search’ from arr[km] till we get x.

  • Best Step size = √arrLength
    •    int step = sqrt((double) arrLength);
  • Complexity:
    • worst case:
      • n/m Jumps
      • if the last checked value is greater than the element to be searched for, we perform ‘m-1’ comparisons more for linear search.
      • (n/m)+(m-1)
      • –> n/m –> Jumps
      • –> m-1 –> Linear Search after Jumps
    • Best Case
      • Step/Jump size ==> (m = √n)
         
  • IMPORTANT:
    • The optimal size of a block to be jumped is (√ n).
      • This makes the time complexity of Jump Search O(√ n).
    • The time complexity of Jump Search is between Linear Search ( ( O(n) ) and Binary Search ( O (Log n) ).
    • Binary Search is better than Jump Search, but Jump search has an advantage that we traverse back only once (Binary Search may require up to O(Log n) jumps.
    • Consider a situation where the element to be searched is the smallest element or smaller than the smallest. So in a system where binary search is costly, we use Jump Search.
/*
Jump Search Algorithm is for SORTED arrays.
This Algorithm check 'fewer elements' (than linear search) by jumping ahead by fixed steps or skipping some elements.
Algorithm:
arr[],
n = size,
m = Steps to Jump,
x = element to find,
* Search for indexex = arr[0], arr[m], arr[2m], ... , arr[km]
* Find an interval as:
arr[km] < x < arr[(k+1)m]
* Perform 'Linear Search' from arr[km] till we get x.
* Best Step size = √arrLength
int step = sqrt((double) arrLength);
Complexity:
worst case:
* n/m Jumps
* if the last checked value is greater than the element to be searched for,
we perform 'm-1' comparisons more for linear search.
worst case:
(n/m)+(m-1)
--> n/m --> Jumps
--> m-1 --> Linear Search after Jumps
Best Step/Jump size ==> (m = √n)
IMPORTANT:
* The optimal size of a block to be jumped is (√ n).
This makes the time complexity of Jump Search O(√ n).
* The time complexity of Jump Search is between Linear Search ( ( O(n) ) and Binary Search ( O (Log n) ).
* Binary Search is better than Jump Search,
but Jump search has an advantage that we traverse back only once (Binary Search may require up to O(Log n) jumps,
* consider a situation where the element to be searched is the smallest element or smaller than the smallest).
So in a system where binary search is costly, we use Jump Search.
Reference:
https://www.geeksforgeeks.org/jump-search/
*/
#include <iostream>
#include <math.h>
using namespace std;
int JumpSearch(int arr[], int x, int arrLength)
{
// Best Step size = √arrLength
int step = sqrt((double) arrLength);
// Jump forward till x is greater than arr[step]
// this is to arrive at a block that contains 'x'.
// Block lies between: arr[prevStep] <--> arr[step].
int prevStep = 0;
while(arr[min(step, arrLength)-1] < x)
{
prevStep = step;
step += sqrt((double)arrLength);
if(prevStep >= arrLength)
return -1;
}
// Linear Search
// In above loop, we arrived at block that may contain 'x'
// now search every index linearly for 'x'
while(arr[prevStep] < x)
{
prevStep++;
// this is condition, when 'x' is not at all present in arr[]
// here, min() gives us the max limit we have to traverse.
// when step is already beyond arrLength, arrLength is our limit to traverse.
// otherwise, step is our limit to traverse linearly.
if(prevStep == min(step, arrLength))
return -1;
}
// return index of x
if(arr[prevStep] == x)
return prevStep;
return -1;
}
int main()
{
int arr[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21,
34, 55, 89, 144, 233, 377, 610 };
int x = 34;
int arrLength = sizeof(arr)/sizeof(arr[0]);
int index = JumpSearch(arr, x, arrLength);
cout << x << " is at index: " << index << endl;
return 0;
}
view raw Jump_Search.cpp hosted with ❤ by GitHub
  • Interpolation Search needs a Sorted Array.
  • 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.
    • For example, if the value of the key is closer to the last element, interpolation search is likely to start search toward the end side.

Partition Logic for Interpolation Search, as Binary Search makes Partition at ‘Mid’ position

  • To find the position to be searched, Interpolation Search uses following formula.
  • The idea of formula is to return:
    • Higher value of ‘pos’ –> when element to be searched is closer to arr[hi].
      • Smaller value of ‘pos’–> when element to be searched is closer to arr[lo] 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:

Rest of the Interpolation algorithm is same except the above partition logic.
1)    In a loop, calculate the value of “pos” using above probe position formula.
       If it is a match, return the index of the item, and exit.
3)    If the item(x) is Less than arr[pos],
       calculate the probe position of the Left sub-array.
       Otherwise calculate the probe position in the Right sub-array.
4)    Repeat until a match is found or the sub-array reduces to zero.\

Time Complexity:

  • If elements are uniformly distributed, then O(log log n)).
  • In worst case it can take upto: O(n).

Auxiliary Space:

  • O(1)
/**
* Reference:
* https://www.geeksforgeeks.org/interpolation-search/
**/
#include <stdio.h>
int interpolationSearch(int arr[], int arrSize, int x)
{
int lo = 0, hi = (arrSize - 1);
// for Interpolation Search, Array needs to be 'Sorted', so (lo <= hi)
// and x must be in array, so (x >= arr[lo]) && (x <= arr[hi])
while((lo <= hi) && (x >= arr[lo]) && (x <= arr[hi]))
{
// 1. (hi-lo)
// 2. (arr[hi]-arr[lo])
// 3. (1)/(2)
// 4. (3) * (x - arr[lo])
int pos = lo + (((double)(hi-lo) / (arr[hi]-arr[lo]))*(x - arr[lo]));
// We got the element
if(arr[pos] == x)
return pos;
// element is Greater, so search in Right side of 'pos'
if(arr[pos] < x)
lo = pos + 1;
// element is Smaller, so search in Left side of 'pos'
if(arr[pos] > x)
hi = pos - 1;
}
// element is not in array
return -1;
}
int main()
{
int arr[] = {10, 12, 13, 16, 18, 19, 20, 21, 22, 23,
24, 33, 35, 42, 47};
int arrSize = sizeof(arr)/sizeof(arr[0]);
int x = 18;
int index = interpolationSearch(arr, arrSize, x);
printf("\n element %d is at index %d", x, index);
return 0;
}
view raw Interpolation_Search.cpp hosted with ❤ by GitHub
  • Find range where element is present
  • Do Binary Search in above found range.

Time Complexity:

  • O(Log i)
  • Auxiliary Complexity:
    • Recursive Binary Search - O(Log n)
    • Iterative Binary Search - O(1)

Usage:

  • Exponential Binary Search is particularly useful for “unbounded searches”, where size of array is infinite.
  • It works better than Binary Search for bounded arrays, and also when the element to be searched is closer to the first element.
/*
Exponential Search:
1. Find range where element is present
2. Do Binary Search in above found range.
Time Complexity:
O(Log i)
--> i --> is the index where 'x' searched elemnet will be.
detail:
https://en.wikipedia.org/wiki/Exponential_search#Performance
Auxiliary Complexity:
Recursive Binary Search - O(Log n)
Iterative Binary Search - O(1)
Usage:
Exponential Binary Search is particularly useful for "unbounded searches", where size of array is infinite.
It works better than Binary Search for bounded arrays, and also when the element to be searched is closer to the first element.
Reference:
https://www.geeksforgeeks.org/exponential-search/
*/
#include <iostream>
#include <algorithm>
using namespace std;
int BinarySearchIterative(int arr[], int left, int right, int x)
{
while(left <= right)
{
int midIndex = left + (right-left)/2;
if(arr[midIndex] == x)
return midIndex;
// if x is greater than midIndex value, search in right half of array
if(arr[midIndex] < x)
left = midIndex + 1;
// if x is less than midIndex value, search in left half of array
else
right = midIndex - 1;
}
return -1;
}
int exponentialSearch(int arr[], int arrSize, int x)
{
// if 'x' is present at 1st location itself
if(arr[0] == x)
return 0;
// find range of indices covering 'x'
// double the index everytime 'x' is not found in previous iteration
int i = 1;
while(i < arrSize && arr[i] <= x)
i = i * 2;
// Perform Binary Search on the identified range
// i/2 --> as we have already identified range, so no need to search in beginning of array
// min() --> as doubling of 'i' may go out of array length, so minimum of 'i' or 'x'
return BinarySearchIterative(arr, i/2, std::min(i, arrSize), x);
}
int main()
{
// Array needs to be Sorted
int arr[6] = {12, 20, 23, 45, 57, 76};
//int arr[] = {2, 3, 4, 10, 40};
int arrLength = sizeof(arr)/sizeof(int);
int result = exponentialSearch(arr, arrLength, 20);
(result == -1)? printf("Element is not present in array")
: printf("Element is present at index %d",
result);
return 0;
}
view raw Exponential_Search.cpp hosted with ❤ by GitHub
  • Time Complexity: O(Log3(n))
#include <iostream>
using namespace std;
// A recursive ternary search function. It returns location of x in
// given array arr[l..r] is present, otherwise -1
int ternarySearch(int arr[], int l, int r, int x)
{
if (r >= l)
{
int mid1 = l + (r - l)/3;
int mid2 = mid1 + (r - l)/3;
// If x is present at the mid1
if (arr[mid1] == x) return mid1;
// If x is present at the mid2
if (arr[mid2] == x) return mid2;
// If x is present in left one-third
if (arr[mid1] > x) return ternarySearch(arr, l, mid1-1, x);
// If x is present in right one-third
if (arr[mid2] < x) return ternarySearch(arr, mid2+1, r, x);
// If x is present in middle one-third
return ternarySearch(arr, mid1+1, mid2-1, x);
}
// We reach here when element is not present in array
return -1;
}
int main()
{
// Array needs to be Sorted
int arr[6] = {12, 20, 23, 45, 57, 76};
int arrLength = sizeof(arr)/sizeof(int);
cout << ternarySearch(arr, 0, arrLength-1, 57);
return 0;
}
view raw Ternary_Search.cpp hosted with ❤ by GitHub
References:
Search