Search rotated and sorted array

#1

question–>
https://practice.geeksforgeeks.org/problems/search-in-a-rotated-array/0#
code–>


it is not giving correct answer

#2

what is the different between these two questions
https://hack.codingblocks.com/app/contests/1617/496/problem
https://hack.codingblocks.com/app/contests/1617/1044/problem
what is the different between these problem? both uses binary search right?

#3

Have updated your code here, also have added comments too


Keep constraints in mind as they might cause an issue.

#4

Both the questions are same, as in both we have to return index which is having a value in a rotated array.

#5

@mr.encoder your code is not giving correct answer for second testcase

#6 
#include <iostream>

using namespace std;

int find(int *arr,int k, int n){

    int s=0;

    int e=n-1;//updated (why are making it n-1 because it is already n-1 right?)

    while(s<e){

        int mid=(s+e)/2;

        if(arr[mid]==k){

            return mid;

        }

        else if(arr[mid]>=arr[s]){

            if(arr[s]<=k and k<=arr[mid]){

                e=mid-1;

            }

            else{

                s=mid+1;

            }

        }

       // else if(arr[mid]<=arr[e]){ updated

            else if(k>=arr[s] and k<=arr[e]){(here what are you doing, we have check if the element is the right part right)

                s=mid+1;

            }

            else{

                e=mid-1;

            }

       // }

    }

    return -1;

}

int main() {

    //code

    int t;

    cin>>t;

    while(t--){

        int n;cin>>n;

        int arr[10001];

        

        for(int i=0;i<n;i++){

            cin>>arr[i];

        }

        int k;cin>>k;

        cout<<find(arr,k,n-1)<<endl;

    }

    return 0;

}
#7 
int find(int *arr,int k, int n){
    int s=0;
    int e=n-1;//cause value of begin is from 0 and at place n is nothing but null value
    while(s<=e){
        int mid=(s+e)/2;
        if(arr[mid]==k){
            return mid;
        }
        if(arr[mid]>=arr[s]){
            if(arr[s]<=k and k<=arr[mid]){
                e=mid-1;
            }
            else{
                s=mid+1;
            }
        }
       // else if(arr[mid]<=arr[e]){ updated
            else{
              if(k>=arr[mid] and k<=arr[e]){/*here what i am doing is If arr[l..mid] first subarray is not sorted, then arr[mid... e] 
    must be sorted subarray */
                s=mid+1;
              }
              else{
                  e=mid-1;
              }
            } 
       // }
    }
    return -1;
}
#8

Later it was

k>=arr[s] and k<=arr[e]) by mistake

It should be

k>=arr[mid] and k<=arr[e]
#9

have posted it on ide for your convenience


Check this

#10

@mr.encoder from below in function call itself i am passing n-1

#11

Haven’t seen your main function. If that’s the case then don’t do e = n-1
rest everything is fine

#12

thanks @mr.encoder it passed all testcases

#13

Resolve mark krdu? I like when you bring issues in my code though :smile:

#14

then i will mark it resolved, okay bhai u can mark it resolved

#15

Sure , marking it as resolved

#16

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.