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