Binary search in sorted duplicate values

Question

Does normal binary search always gives first element in case duplicate value are present in sorted vector ?

Answer 1

Ketan Lalcheta No, your implementation returns just some element - not necessarily the first one.

Imagine, for example, that your array has all zeroes and you search for a zero, then a zero in the middle will be returned.

Answer 2

If you mean std::binary_search, it returns bool telling if the value is in the sequence.

There are also std::lower_bound, returning an iterator to the first element, std::upper bound, returning an iterator after the last element, and std::equal_range returning both.

If your question is about implementing your own binary search, then it depends on how you implement it.

Answer 3

Thanks for response .

I am concern about own implemented binary search. Please refer function named as implementBinarySearch() into code link https://code.sololearn.com/cWWWnWFAjdIy.
For this case, does it always return lowest index in case our element to search is occurring more than once in sorted duplicate input?

Answer 4

Yeah true example... Thanks