Którą wartość zwróci wyszukiwania binarnego

Question

Jeżeli w ciągu liczb występują wartości takie same, czyli x1 <= x2 <= … <= xi = xj = … = xl <= … <= xn

oraz xi = xj = … = xl =y to którą wartość zwróci algorytm wyszukiwania binarnego?

Answer 1

Zależy od implementacji. Przykład z c++ wypluty przez chatgpt, który porównuje lower_bound z upper_bound, które prawdopodobnie są zaimplementowane przy użyciu binary search:

#include <iostream>
#include <algorithm>
#include <vector>

int main() {
  std::vector<int> sorted_vec {1, 2, 3, 4, 5, 6, 7, 7, 7, 8, 9};

  int middle_element = 7;
  auto lower = std::lower_bound(sorted_vec.begin(), sorted_vec.end(), middle_element);
  auto upper = std::upper_bound(sorted_vec.begin(), sorted_vec.end(), middle_element);

  std::cout << "The lower bound of " << middle_element << " is " << std::distance(sorted_vec.begin(), lower) << std::endl;
  std::cout << "The upper bound of " << middle_element << " is " << std::distance(sorted_vec.begin(), upper) << std::endl;

  return 0;
}

Output:

The lower bound of 7 is at position 6
The upper bound of 7 is at position 9