Interpolation search

Interpolation search (sometimes referred to as extrapolation search) is an algorithm for searching for a given key value in an indexed array that has been ordered by the values of the key. It parallels how humans search through a telephone book for a particular name.

On average the interpolation search makes about log(log(n)) comparisons. In the worst case it can make up to O(n).

In each search step it calculates where in the remaining search space the sought item might be, based on the key values at the bounds of the search space and the value of the sought key, usually via a linear interpolation.

CODE

public int interpolationSearch(int[] Array, int key){

int low = 0;
int high = Array.length – 1;
int mid;

while (Array [low] <= key && Array [high] >= key) {

mid = low + (high – low) / (Array[high] – Array[low]) *( key – Array[low]);

if (Array [mid] < key)
low = mid + 1;
else if (Array [mid] > key)
high = mid – 1;
else
return mid;
}

if (Array [low] == key)
return low;
else
return -1; // Not found
}

An array is rotated at an unknown position. Find minimum element in the array.

Given a sorted array of distinct elements

int MinimumRotatedArray(int A[], int l, int r)
{
    if( A[l] <= A[r] )
        return l;

while( l <= r )
{
if( l == r ) {return l;}

int mid = Math.floor((l + r) / 2);
if( A[mid] < A[r] )
r = mid;
else
l = mid+1;
}
return -1;
}

Find number of occurrences of input ‘key’ in log N time

Given a sorted array with possible duplicate elements

int first(int A[], int l, int r, int key)
{
    if(r >= l)
    {
        int mid = (l + r)/2;
        if( ( mid == 0 || key > A[mid-1]) && A[mid] == key)
             return mid;
        else if(key > A[mid])
              return first(A, (mid + 1), r, key);
         else
              return first(A, l, (mid -1), key);
     }
     return -1;
}
 
 int last(int A[], int l, int r, int key)
 {
     if(r – l >= 1)
     {
          int mid = (l + r)/2;
          int n = sizeof(A)/sizeof(A[0]);
          if(( mid == n-1 || key < A[mid+1]) && A[mid] == key )
               return mid;
           else if(key < A[mid])
                return last(A, l, (mid -1), key);
           else
                 return last(A, (mid + 1), r, key);      
        }
        return -1;
}

int count(int A[], int key)
{
    int i = first(A, 0, n-1, key);
    int j = last(A, i, n-1, key);  
   
     return j-i+1;       //gives number of occurences of 'key'
}

Given an array of N distinct integers, find floor and ceil value of input ‘key’

Say, A = {-1, 2, 3, 5, 6, 8, 9, 10} and key = 7, we should return 6 as floor value and 8 as ceil value.

For returning floor value

int binarySearch(int arr[], int l, int r, int x)
{
    while( r - l > 1 ){
        int mid = Math.floor((l + r) / 2);
        if (arr[mid] > x) return binarySearch(arr, l, mid, x);
        if (arr[mid] < x) return binarySearch(arr, mid, r, x);
     }
     return arr[l];    
}

For returning ceil value

return arr[r]; 

 

Binary search

Using Recursion

int binarySearch(int arr[], int l, int r, int x)
{
    if (l > r) {return -1;}
    int mid = Math.floor((l + r) / 2);
    if (arr[mid] > x) return binarySearch(arr, l, mid-1, x);
    if (arr[mid] < x) return binarySearch(arr, mid+1, r, x);
    return mid;
}

Using Iterative

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

Leap year algo

function isLeapYear (year):
    if ((year % 4 == 0) && (year % 100 != 0)) || (year % 400 == 0)
        then true
    else false

Runtime concepts

Recurrence tree of T(n) = aT(n/b) + f(n),

• Work done at root is f(n)

• Work done at all leaves is    where c is

• Height of recurrence tree is 

Also note:

 

• O(1): If it doesn’t contain loop, recursion and call to any other non-constant time function

• O(n): If the loop variables is incremented / decremented by a constant amount

• O(n^c): Time complexity of nested loops is equal to the number of times the innermost statement is executed

• O(Logn): If the loop variables is divided / multiplied by a constant amount.

• O(LogLogn): If the loop variables is reduced / increased exponentially by a constant amount.

Master theorem

The master theorem concerns recurrence relations of the form:

• n is the size of the problem.

• a is the number of subproblems in the recursion.

• n/b is the size of each subproblem. (Here it is assumed that all subproblems are essentially the same size.)

• f (n) is the cost of the work done outside the recursive calls.

Case 1

If   

Where  

Then 

Case 2

If   k ≥ 0 and 

Where 

Then 

Case 3

If     where 

and    for some constant and sufficiently large n

Then 

Count the number of occurrences of each letter in string

const char *str = "The quick brown fox jumped over the lazy dog.";

int counts[256] = { 0 };
int i;
size_t len = strlen(str);

for (i = 0; i < len; i++) {
counts[(int)(str[i])]++;
}

for (i = 0; i < 256; i++) {
printf(“The %d. character has %d occurrences.\n”, i, counts[i]);
}