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).
  • 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.
  • 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.
  • 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)
  • 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.
  • Time Complexity: O(Log3(n))
References:
Search