Behavior of lower_bound in cpp on unsorted array

Question

I wanted to ask how lower_bound in cpp ( C++ ) behaves when it is applied on unsorted array. I mean when I ran the following program.

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
    int arr[]={8,9,10,1,2,3};
    auto itr= lower_bound(arr,arr+6,7);
    cout<<*itr<<endl;
}

it gave the output as '2'. But according to definition of lower_bound, it gives the iterator to first element which fails '<' with 'val'. So according to this definition, shouldn't the answer be '8', because "8 is not less than 7". I know it works on sorted array, but I want to know whether or not, there is a logic behind this value or is it a junk.

Thanks.

Averett

Violating preconditions for standard library functions results in undefined behaviour. – Liam

It doesn't work and the answer is junk. If you're really interested how the answer came out to be 8, check the implementation of the function. – Clouse

Answer 1

Since the precondition of supplying a sorted array has been violated, the behavior is undefined. Your code demonstrates undefined behavior twice: first, when you pass an unordered array to lower_bound, and second, when you dereference iter without comparing it to arr+6 first.

It is easy to see what is going on, though: the algorithm behind lower_bound is a basic binary search. You give the algorithm an array, it divides them in two halves, and checks the item in the middle. You supplied an even number of items, there are two numbers that can be considered "being in the middle" - 10 and 1. It looks like the algorithm picked 1, compared it to your search item 7, and continued search in the upper half of the array, checks 2 and 3, and finally returns the pointer pointing past the end of the array.

When you dereference that pointer, you get junk; unfortunately, it happens to match one of the elements of your array, i.e. 2, leading you to a wrong conclusion.

Change your code as follows to see what is actually returned:

int arr[]={8,9,10,1,2,3, -1};

Now dereferencing the element at index 6 is valid; your code should probably print -1 (although this is an exploit of undefined behavior specific to your particular system, and it is not guaranteed to produce the same results on other systems).

Guayaquil

This seems like a rational explanation. But @dasblinkenlight going by your explanation answer to {16,15,4,3,1}, lower_bound(arr,arr+5,4), should be 4 because it will choose 4 as first element and 4 is not less than 4. So should return this. But it actually returns 16. It is always the case ie first element is returned. Can you please explain this behavior. – Averett

@Averett lower_bound finds 4, picks the left part of the array, and tries to find the first 4 in a possible sequence of multiple 4s. Its choices are 16 and 15 at this point. It picks 16, sees that it's greater than the search item 4, and says that the place of 4 is right in front of it - i.e. at the beginning of the sequence. – Guayaquil