Suppose you are 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. You have to design an O(nlogn) code to find the value of k | PU | Past Paper 2017

on

UNIVERSITY OF THE PUNJAB

Fourth Semester 2017

Examination: B.S. 4 Years Programme 

Paper: Data Structure and Algorithm

Course Code: IT-207 / IT-22408

Long Questions

b) Suppose you are 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 is an example of n=16 elements with k=10.

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

You have to design an O(nlogn) code to find the value of k.

int FindK(int A[], int size) //code to find the value of k.

int FindK(int A[], int size) 

int FindK(int arr[], int l, int h, int key)
{
    if (l > h) 
  return -1;
    int mid = (l+h)/2;
    if (arr[mid] == key) 
  return mid;
    /* If arr[l...mid] is sorted */
    if (arr[l] <= arr[mid])
    {
        /* As this subarray is sorted, we can quickly
        check if key lies in half or other half */
        if (key >= arr[l] && key <= arr[mid])
         return FindK(arr, l, mid-1, key);
  else
         return FindK(arr, mid+1, h, key);
    } 
    /* If arr[l..mid] is not sorted, then arr[mid... r]
    must be sorted*/
    if (key >= arr[mid] && key <= arr[h])
        return FindK(arr, mid+1, h, key);
  else
     return FindK(arr, l, mid-1, key);
}
int main()
{
    int arr[] = {4, 5, 6, 7, 8, 9, 1, 2, 3};
    int n = sizeof(arr)/sizeof(arr[0]);
    int key = 6;
    int i = FindK(arr, 0, n-1, key); 
    if (i != -1)
     cout << "Index: " << i << endl;
    else
     cout << "Key not found";
}

Let me know in the comment section if you have any question.

Previous Post:
Write down the code of the following function of Link List Class. i) void removeFromHead() ii) int countDuplicate(int key) | PU | Past Paper 2017



Comments

Post a Comment