0

I'm learning about the lower_bound function in C++. To give an example, the author gives the following piece of code:

auto k = lower_bound(array,array+n,x)-array;
if (k < n && array[k] == x) {
// x found at index k
}

I understand that the type of k will be a pointer that holds the address of either the found value or the element after the last element in the array. I, however, don't fully understand the purpose of subtracting the array from the value we get from the lower_bound function. If someone could explain the purpose behind this, I'd really appreciate it. Thanks in advance.

discovery
  • 43
  • 6
  • 1
    C-style arrays "decay" to pointers to their first elements when used. So, just think of `&(array[0])`, and what remains is just pointer arithmetic, as `std::lower_bound` will return a pointer, when given a pointer as the iterator type. – einpoklum Jan 12 '22 at 11:55
  • lower_bound returns a pointer to an array element, and you are subtracting the pointer to first element of the array from it. – kiner_shah Jan 12 '22 at 11:55
  • `array[k]` is the value of the thing at the address of `array` plus `k` (i.e. k needs to be one of 0, 1, ... n-1.) – doctorlove Jan 12 '22 at 11:56
  • It is code that is not communicating intent very well (and reads more like someone tyring to be smart) The code is full of holes, makes assumptions on the content of the array (weakly sorted), can access the array out of bounds (array+n) and is substracting a pointer from an iterator (unrelated types). For looking up things in a container use std::find_if (and if you really need the index read this: https://stackoverflow.com/questions/2152986/what-is-the-most-effective-way-to-get-the-index-of-an-iterator-of-an-stdvector) – Pepijn Kramer Jan 12 '22 at 12:14
  • The code is unnecessarily complicated: If no element >= x is found array+n is returned. Therefore, the test is simply `auto k = lower_bound(array,array+n,x); if( k != array+n && array[k] == x) ) { /* found x */ }`: Has anything larger or equal be found at all, and is it equal. I suppose `std::find()` would be better here. – Peter - Reinstate Monica Jan 12 '22 at 12:22
  • The almost literally identical question was asked [here](https://stackoverflow.com/questions/65129165/why-is-subtracting-an-array-from-lower-bound-return-a-dereferenced-value). Somebody must have put this (bad) example on the web around that time. To the OP: Would you care to give us your source? (Perhaps here: https://icpc.ninja/Algorithms/Linear/LowerAndUpperBounds/) The context is that by obtaining indexes for upper and lower bound in a fully sorted array you can count the number of occurrences. – Peter - Reinstate Monica Jan 12 '22 at 12:29
  • But the quoted page is not correct in saying that "the functions" (apparently referring to lower_bound, upper-bound, equal_range) require sorted ranges. The search range only needs to be *partitioned* (C++20 ISO std 25.8.4.1). – Peter - Reinstate Monica Jan 12 '22 at 12:38

1 Answers1

-2

lower_bund will return us a pointer to the element that is not bigger than passed value in the array. Of course we should remember that lower_bound works as we expect only with sorted arrays. Since an array is a sequential set of elements, we can find out the displacement of one element relative to another by subtraction. In other words, subtracting array from lower_bound(), we find the index of the element returned to us by lower_bound()

Deumaudit
  • 978
  • 7
  • 17
  • 1
    "lover_bund [sic] will return us a pointer to the found element in the array" - no it doesn't. It returns the pointer to the earliest place where the searched-for element would be if it was there, assuming the array is weakly sorted. The rest of the answer is broadly correct although you do need to talk about why pointer arithmetic is valid if `end()` is returned. – Bathsheba Jan 12 '22 at 12:01
  • You really should proof-read your post. Not sure what "lovers" or "bunds" have to do with this ;) | Also, posting answers on duplicates is generally frowned upon. – Dan Mašek Jan 12 '22 at 21:56
  • @DanMašek I answered question before it was marked duplicate. And about lovers, Yeah, my bad – Deumaudit Jan 13 '22 at 06:34