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;
}