Searching Problem List

  1. Interpolation Search. Youtube. GFS.  The search works well for uniformly distributed numbers. 
    Formula Calculation –

    So the formula to estimate the position =

    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[]

    To implement this code, we proceed just like binary search. Instead of mid we use this pos and increase/decrease it accordingly. 
    Time complexity = O (log log n))



  2. Recursively implement a linear search. 

  3. Given a sorted array with possible duplicate elements. Find number of occurrences of input ‘key’ in log N time.

  4. *** Suppose you have a sorted array of infinite numbers, how would you search an element in the array?
    Algo: We find the range to search using exponential search. The apply binary search.


  5. Jump Search is a searching algorithm for sorted arrays. 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. GFG.
    We need to find the range in which the number lies. So we check if the number lies in step, the size of step being √n.  Check the code as it’s pretty clear and simple.
    –  Works only sorted arrays.
    –  The optimal size of a block to be jumped is O(√ 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) ).
    Jump search does a linear search after finding range while exponential search does binary search after finding range.


  6. Exponential Search. Jump search does a linear search after finding range while exponential search does binary search after finding range. It involves two steps:
    1. Find range where element is present
      Here we increase step in size of 2, ie we keep doubling the step size. In Jump search we increase step in size of √n..
    2. Do Binary Search in above found range.
      Once we find an index i (after repeated doubling of i), we know that the element must be present between i/2 and i. now do a binary search in i and i/2
    while (i < n && arr[i] <= x)
            i = i*2;

  7. ** Find next greater number with same set of digits. GFG

  8. Binary Search

  9. *** Binary Search 
    Set 3 – Q5, Q12
    Set 2 – Q5, Q7, Q12
    Set 1 – Q26Q24, Q23, Q20
Advertisements

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s