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.

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).