mirror()

Change a tree so that the roles of the left and right pointers are swapped at every node.




/*
 * Mirror image of given tree
 */
void mirror(nodeptr node)
{
    nodeptr temp;
    if(node != NULL)
    {
        temp = node->left;
        node->left = node->right;
        node->right = temp;
        mirror(node->left);
        mirror(node->right);
    }
}

Suppose that in addition to being sorted, the entries of A are distinct integers. Design an efficient algorithm for finding an index i such that A[i]=i or indicating that no such index exists. 

We can apply binary search technique for this too as we are aware that array is sorted and have distinct elements.

Below is the working code in C

#include<stdio.h>
int bsearch(int a[],int size)
{
    int low=0;
    int up=size-1;
    int mid;
    while(low <= up) {
        mid=(low+up)/2;
        if(a[mid]==mid)
            return mid;
        else if(a[mid]<mid)
            low = mid+1;
        else
            up = mid-1;
    }
    return -1;
}
int main()
{
    int arr[10]={-1,0,2,4,6,8,10,12,14,15};
    int pos;
    pos=bsearch(arr,10);
    if(pos == -1)
        printf("element for a[i] == i is not found\n");
    else
        printf("element for a[i] == i is at location %d\n",pos+1);
    return 0;
}
 

Design an efficient algorithm that finds the index of first occurance of an element larger than a specified key k; return -1 if every element is less than or equal to k.

This can also be solved by doing little modification in binary search program. Below is the fully working code in C.

#include<stdio.h>
int bsearch(int a[],int size,int elem)
{
    int low=0;
    int up=size-1;
    int mid;
    while(low <= up) {
        mid=(low+up)/2;
        if(a[mid]==elem)
        {        if(mid+1 <= up)
                    if(a[mid+1]>elem)
                        return mid+1;
                    else
                        low = mid+1;
                else
                    return -1;
        }
        else if(a[mid]<elem)
        {
            low = mid + 1;
            if(a[low]>elem)
                return low;
        }
        else
        {
            up = mid -1;
            if(a[up]<=elem)
                return up+1;
        }
    }
    return -1;
}
int main()
{
    int arr[10]={1,2,3,3,4,6,9,9,9,10};
    int pos,srch_elem;
    printf("Enter element to search : ");
    scanf("%d",&srch_elem);
    pos=bsearch(arr,10,srch_elem);
    if(pos == -1)
        printf("element greater than %d is not in array\n",srch_elem);
    else
        printf("first element greater than %d is %d at location %d\n",srch_elem,arr[pos],pos+1);
    return 0;
}

Write a program that takes a sorted array A and a key elem and returns the index of first occurance of key in A, and returns -1 if key doesnot appears in A.

Above problem can be solved by doing simple modification of binary search program. Below is the working code in C.

#include<stdio.h>
int bsearch(int a[],int size,int elem)
{
        int low=0;
        int up=size-1;
        int mid;
        while(low <= up) {
                mid=(low+up)/2;
                if(a[mid]==elem)
                {       if(a[mid-1] == elem)
                                up=mid-1;
                        else
                                return mid;
                }
                else if(a[mid]<elem)
                        low=mid+1;
                else
                        up=mid-1;
        }
        return -1;
}
int main()
{
        int arr[10]={1,3,3,3,3,6,9,9,9,10};
        int pos,srch_elem;
        printf("Enter element to search : ");
        scanf("%d",&srch_elem);
        pos=bsearch(arr,10,srch_elem);
        if(pos == -1)
                printf("%d is not in array\n",srch_elem);
        else
                printf("first occurance of %d is at location %d\n",srch_elem,pos+1);
        return 0;
}

Binary Search

Searching

Given an arbitrary collection of n keys, the only way to determine if a search key is present by examining each element which yields O(n) complexity.
If the collection is organized, searching can be speed up dramatically.

Binary Search

Binary search is a natural divide-and conquer strategy for searching. The idea is to eliminate half the keys from consideration by keeping the keys in a sorted array. If the search key is not equal to the middle element of the array, one of the two sets of keys to the left and to the right of the middle element can be eliminated from further consideration.

Below is the working code in C Language.

#include<stdio.h>
int bsearch(int a[],int size,int elem)
{
        int low=0;
        int up=size-1;
        int mid;
        while(low <= up) {
                mid=(low+up)/2;
                if(a[mid]==elem)
                        return mid;
                else if(a[mid]<elem)
                        low=mid+1;
                else
                        up=mid-1;
        }
        return -1;
}
int main()
{
        int arr[10]={1,2,3,4,5,6,7,8,9,10};
        int pos,srch_elem;
        printf("Enter element to search : ");
        scanf("%d",&srch_elem);
        pos=bsearch(arr,10,srch_elem);
        if(pos == -1)
                printf("%d is not in array\n",srch_elem);
        else
                printf("%d is at location %d\n",srch_elem,pos+1);
        return 0;
}

Here in the above program of binary search there is a bug. The error is in assignment mid = (low+up)/2; it can lead to overflow (in case of array size large approx equal to size of int) and hence should be replaced by mid = low + (up-low)/2 .

The time complexity of binary search is equal to O(logn), which is superior to O(n) approach needed when the keys are unsorted.