Why is binary_search not working as expected?

Question

The question is to find the index of first element in the array that repeats itself atleast once in the array.

Input:

7

1 3 4 5 3 7 2

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

int main()
{
    int n;
    cin >> n;

    int a[n], curr = -1;
    int num = sizeof(a) / sizeof(a[0]);

    for (int i = 0; i < n; i++)
        cin >> a[i];

    for (int i = 0; i < n; i++)
    {
        int x = a[i];
        a[i] = -1;
        if (binary_search(a, a + num, x))
        {
            curr = i;
            cout << curr << endl;
            break;
        }
    }
    cout << curr + 1;
    return 0;
}

Expected Output: 2 (As 3 is the first element to appear twice in the array)

Output received: 0

Off topic: whatever resource you are using to learn C++, stop using it immediately. `bits/stdc++` isn't a standard header, and should never be used. Arrays must have compile time constant sizes, not user specified. And never use namespace std. — ChrisMM, Feb 12 '22 at 04:50
`num` is going to have the wrong value, btw. Just use `n`, which already contains the number of elements. — ChrisMM, Feb 12 '22 at 04:57
Also, since this `int a[n]` is not a valid C++ array, doing this: `binary_search(a, a + num, x)`, where you are adding `num` to `a` is ... we don't know if that actually does what it says. As a matter of fact, certain compilers that allowed the non-standard syntax of `int a[n]` did not work with STL algorithm functions. Instead, weird syntax errors were given when using arrays in this manner. — PaulMcKenzie, Feb 12 '22 at 05:22
Binary search assumes a sorted range. You are not supplying it a sorted range, so its behaviour is undefined. Also, `int a[n]` where `n` is a variable is not valid in standard C++. — Peter, Feb 12 '22 at 12:59

score 1 · Accepted Answer · answered Feb 12 '22 at 05:07

cin >> n;

int a[n]

This isn't allowed in C++. The size of an array variable must be compile time constant. n is not compile time constant. To create an array of runtime length, you must allocate it dynamically. Simplest solution is to use std::vector,

int num = sizeof(a) / sizeof(a[0]);

Use std::size(a) to get the size of an array instead. However, in this case, just use n.

binary_search(a, a + num, x)

The input range must be partially sorted in order to use std::binary_search with respect of the searched number. Since you use potentially all elements as the searched number, this effectively means that the array must be fully sorted.

Input:

7

1 3 4 5 3 7 2

Your input array is not fully sorted. As result of violating the pre-condition, the behaviour of the program is undefined.

Why is binary_search not working as expected?

1 Answers1