CODEWITHSUNDEEP
c++arraysalgorithmvectorbinary-search
amlansahoo07
amlansahoo07

Reputation: 3

binary_search() function doesn't work in my function body

The question is -

Given a sorted and rotated array A of N distinct elements which is rotated at some point, and given an element K. The task is to find the index of the given element K in the array A.

Input: The first line of the input contains an integer T, denoting the total number of test cases. Then T test cases follow. Each test case consists of three lines. The first line of each test case contains an integer N denoting the size of the given array. The second line of each test case contains N space-separated integers denoting the elements of the array A. The third line of each test case contains an integer K denoting the element to be searched in the array.

Output: For each test case, print the index (0 based indexing) of the element K in a new line, if K does not exist in the array then print -1.

User Task: Complete Search() function and return the index of the element K if found in the array. If the element is not present, then return -1.

Expected Time Complexity: O(log N).

Expected Auxiliary Space: O(1).

Constraints:

1 ≤ T ≤ 100
1 ≤ N ≤ 107
0 ≤ Ai ≤ 108
1 ≤ K ≤ 108

Example:
Input:
3
9
5 6 7 8 9 10 1 2 3
10
3
3 1 2
1
4
3 5 1 2
6
Output:
5
1
-1

MY SOLUTION FOR THE REQUIRED FUNCTION:- 

// vec : given vector of elements  
// K : given value whose index we need to find   

int Search(vector<int> vec, int K) 
{
    if(binary_search(vec.begin(),vec.end(), K))
    {
        return 1;
    }
    else return -1;
}

This is not the logic for the question, but I was aiming for an approach which would first require me to find whether an element is present in the vector.
But here the output for my code when the above mentioned test cases are given is:-
-1
-1
-1
which indicates that the element isn't found in any cases whereas it's actually present in the vector in the first two cases. Where am I going wrong ??

Upvotes: 0

Views: 103

Answers (2)

Alberto
Alberto

Reputation: 12939

One of the preconditions of std::binary_search as you can see here, is that the array where you are searching on, must be sorted, instead you can write your own linear search:

template<class Iterator, class ToFind>
bool linear_search(Iterator start, Iterator end, const ToFind& element){
   while(start != end){
      if(*start == element)
          return true;
      std::next(start);
   }
   return false;
}

As @Blastfurnace has pointed out, you can use std::find which will do this (but probably better)

Upvotes: 1

Vasilyev Marat
Vasilyev Marat

Reputation: 31

Binary search means you have already sorted array. All of your input arrays aren't sorted

Upvotes: 0

Related Questions