2013 Qno3(b)

 Suppose you're given a sorted array A of n distinct numbers that has been rotated k steps, for some unknown integer k between 1 to n-1. That is A[1...k] is sorted in increasing order, and A[k+1...n] is also sorted in increasing order, and A[n]<A[1]

The following array A is an example of n=16 elements with k=10

    A={9, 13, 16, 18, 19, 23, 26, 31, 37, 42, 0, 1, 2, 5, 7, 8}

You have to design 0(log n) code to find the value of k.

int FindK(int A[], int size) //you have to implement this function

ANSWER:

#include<iostream>

using namespace std;

//FIND K

int FindK(int A[], int size){

int low, high=size-1;

while(low<=high){

if(A[low]<=A[high])

return low;

int mid=(low+high)/2;

int next=(mid+1)%size; 

int prev=(mid+size-1)%size;

if(A[mid]<=A[next]&&A[mid]<=A[prev])

return mid;

else if(A[mid]<=A[high])

high=mid-1;

else if(A[mid]>=A[low])

low=mid+1;

}

return -1;

}

//MAIN

int main(){

int A[]={9, 13, 16, 18, 19, 23, 26, 31, 37, 42, 0, 1, 2, 5, 7, 8};

cout<<FindK(A, 16);

}

//YOU CAN CHECK OUT THIS VIDEO TO UNDERSTAND THINGS FURTHUR