here in this code i am facing issues regarding my output of find the correct index for the key. the output of pivot element is correct but i was unable for find the error in the key index part of my code . can some debug it for me please or at least tell me where i was doing it wrong.

this is a code of me trying to find the index of key element in a sorted rotated array and my approach is as follows first i have to find the pivot element than i compare the size of element at pivot index and size of key element if the size is greater than pivot and less the size of array than i binary search between pivot and ( n -1 ) : which the last index of array . and if the size is small than i search between 0th index and pivot index.

so correct me where i am wrong.

#include<bits/stdc  .h>
using namespace std;

int getPivot ( int arr[] , int size){

    int start =0;
    int end = size-1;

    int mid = start   ( end - start)/2;
    while( start < end ){
        if( arr[mid] > arr[0]){
            start = mid  1;
        }
        else{
            end = mid;
        }
        mid = start   ( end - start )/2;

    }
    return end;
}

int binarySearch ( int arr[] , int size , int s , int e , int key){

    int start = s;
    int end = e;
    int mid = s ( e-s )/2;
    while ( start <= end ){
        if( arr[mid] == key){
            return mid; 
        }
        else if ( arr[mid] > key ){
            end = mid -1;
        }
        else{
            start = mid  1;
        }
        mid = start ( end - start )/2;
    }
    return start ;
}

int main(){

    int n,k;
    cin>>n>>k;

    int arr[n];
    for( int i=0; i<n; i  ){
        cin>>arr[i];
    }

    int pivot = getPivot( arr , n);
    cout<<" the index of Pivot element is : "<<pivot<<endl;

    
    if( k >= arr[pivot] && k<= arr[n-1] ){
        cout<<" the index of the key is : " <<binarySearch( arr , n , pivot , ( n-1) , k)<<endl;
    }
    else{

        cout<<" the index of the key is : " <<binarySearch( arr , n , 0 , (pivot-1) , k)<<endl;
    }
 
    return 0;
}

CodePudding user response：

This looked supsicous:

int mid = s ( e-s )/2;

It's not using modulo arithmetic correctly. There's confusion of comparing arr[mid] with normalized vs. unnormalized coordinates and how that applies to recomputing start and end on each iteration of the binary search loop. You want start and end to be recomputed in the "normalized" space, but mid needs to be adjusted for the pivot index value.

This also looked suspicious int main:

   if( k >= arr[pivot] && k<= arr[n-1] ){
        cout<<" the index of the key is : " <<binarySearch( arr , n , pivot , ( n-1) , k)<<endl;
    }
    else{

        cout<<" the index of the key is : " <<binarySearch( arr , n , 0 , (pivot-1) , k)<<endl;
    }

If I understand the problem correctly, the algorithm takes in a sorted array that could be rotated. Where the input read from stdin could be something like the following:

10 4                        // n = 10, key=4
9 10 11 12 13 1 2 3 4 5     // the sorted rotated array

So in the above example if key==4, then we want to return 8 as the index since array[8] == 4

Here's a cleaned up version of your code. The main changes are this:

1. Use the correct header includes
2. Removed the variable length array and replaced with std::vector.
3. Fixed the bug in binarySearch. Also, the e parameter isn't actually needed with this fix, so I removed that.
4. binarySearch will return -1 if the element can't be found instead of start
5. Fixed main to just call binarySearch with the size and pivot index in a consistent way. No need to have two versions of calling it. Nor do you need to explicitly pass the end index.
6. getPivot had some bugs in it too. So I fixed that with similar modulo arithmetic.

#include <iostream>
#include <vector>

using namespace std;

int getPivot(int arr[], int size) {

    int start = 0;
    int end = size - 1;

    if (size <= 1)
    {
        return 0;
    }

    while (start <= end)
    {
        int len = end - start   1;
        int prev = (start   len-1) % len;
        int mid = (start   end) / 2;
        if (arr[start] < arr[prev])
        {
            return start;
        }

        if (arr[start] <= arr[mid])
        {
            start = mid 1;
        }
        else
        {
            end = mid;
        }
    }

    return -1;
}

int binarySearch(int arr[], int size, int pivot, int key) {

    int start = 0;           // start and end are in the "normalized" index space
    int end = size - 1;
    while (start <= end) {

        int mid = (start   end) / 2;
        int actualMid = (pivot   mid) % size;  // actualMid is the denomalized conversion of mid using modulo arithmetic

        if (arr[actualMid] == key) {
            return actualMid;
        }
        else if (arr[actualMid] > key) {
            end = mid - 1;     // adjust end in normalized index space
        }
        else {
            start = mid   1;   // adjust start in normalized index space
        }
    }
    return -1;
}


int main() {

    int n, k;
    cin >> n >> k;

    std::vector<int> arr(n);
    for (int i = 0; i < n; i  ) {
        cin >> arr[i];
    }

    int pivot = getPivot(arr.data(), n);

    cout << " the index of Pivot element is : " << pivot << endl;
    cout << " the index of the key is : " << binarySearch(arr.data(), n, pivot, k) << endl;

    return 0;
}