Find an element in a sorted array which is rotated.

//INPUT : {6,7,8,0,1,2,3,4,5}
//OUTPUT : number found at index 7

#include<stdio.h>

int bsearch(int a[],int low,int high,int n){
if(high-low <=1){
if(a[low] == n) return low;
else if(a[high] == n) return high;
else return -1;
}
int mid = (low+high)/2;
if(a[mid] > a[low]){
if(n>=a[low] && n<=a[mid]){
return bsearch(a,low,mid,n);
} else {
return bsearch(a,mid+1,high,n);
}
} else {
if(n>=a[mid] && n<=a[high]){
return bsearch(a,mid,high,n);
} else {
return bsearch(a,low,mid-1,n);
}
}
}

int main(){
int a[] = {6,7,8,0,1,2,3,4,5};
int i = bsearch(a,0,sizeof(a)/sizeof(a[0])-1,4);
if(i==-1){
printf("number not found!!");
} else {
printf("number found at index %d",i);
}
return 0;
}

Sorted array is rotated. Find starting point or the index of the minimum element

// INPUT : {7,0,1,2,3,4,5,6}
// OUTPUT : array starts at value=0 and index=1

#include<stdio.h>

int findstartRecur(int a[],int start,int end){
int mid = (start+end)/2;
if(a[start] < a[end]){
return start;
}
if(end-start < 2){
return (a[end] < a[start])?end:start;
}
if(a[mid] > a[start]){
return findstartRecur(a,mid+1,end);
} else{
return findstartRecur(a,start,mid);
}
}

int main(){
int a[] = {7,0,1,2,3,4,5,6};
int start = findstartRecur(a,0,sizeof(a)/sizeof(int)-1);
printf("array starts at value=%d and index=%d",a[start],start);
return 0;
}

Rotating a N X N matrix clockwise by 90 degrees

#include<stdio.h>
#define N 4

void display(int A[][N]){
int i,j;
for(i=0;i<N;i++){
for(j=0;j<N;j++){
printf("%d\t",A[i][j]);
}
printf("\n");
}
}

void rotate(int A[][N]){
int i,j;
int temp;
for(j=0;j<N/2;j++){
for(i=0;i<N-1-2*j;i++){
temp = A[j][i+j];
A[j][i+j] = A[N-1-i-j][j];
A[N-1-i-j][j] = A[N-1-j][N-1-i-j];
A[N-1-j][N-1-i-j] = A[i+j][N-1-j];
A[i+j][N-1-j] = temp;
}
}
}

int main(){
int A[N][N] = {{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16}};
//int A[N][N] = {{1,2,3},{4,5,6},{7,8,9}};
printf("original matrix :\n");
display(A);
rotate(A);
printf("after rotating 90deg clockwise :\n");
display(A);
return 0;
}