Бинарный поиск для нахождения наименьшего и наибольшего элемента в отсортированном массиве, чем заданное значение?
Таким образом, я пытался реализовать алгоритм бинарного поиска (как можно более общий, который может адаптироваться к различным случаям). Я искал это в интернете, и некоторые используют, while (low != high) и некоторые используют, while (low <= high) и некоторые другие различные условия, которые очень запутывают.
Основной код:
#include <iostream>
#include <map>
#include <vector>
#include <string>
#include <utility>
#include <algorithm>
#include <stack>
#include <queue>
#include <climits>
#include <set>
#include <cstring>
using namespace std;
int arr1[2000];
int n;
int main (void)
{
int val1,val2;
cin>>n;
for (int i = 0; i < n; i++)
cin>>arr1[i];
sort(arr1,arr1+n);
cout<<"Enter the value for which next greater element than this value is to be found";
cin>>val1;
cout<<"Enter the value for which the first element smaller than this value is to be found";
cin>>val2;
int ans1 = binarysearch1(val1);
int ans2 = binarysearch2(val2);
cout<<ans1<<"n"<<ans2<<"n";
return 0;
}
int binarysearch1(int val)
{
while (start <= end)
{
int mid = start + (end-start)/2;
if (arr[mid] <= val && arr[mid+1] > val)
return mid+1;
else if (arr[mid] > val)
end = mid-1;
else
start = mid+1;
}
}
Аналогично, для нахождение первого элемента, который меньше данного элемента,
int binarysearch2(int val)
{
while (start <= end)
{
int mid = start + (end-start)/2;
if (arr[mid] >= val && arr[mid] < val)
return mid+1;
else if (arr[mid] > val)
end = mid-1;
else
start = mid+1;
}
}
Я часто очень запутываюсь, когда мне приходится модифицировать бинарный поиск для такой абстракции. Пожалуйста, дайте мне знать, если есть более простой метод для того же? Спасибо!
5 ответов:
Как вы сказали, существуют различные способы выражения конечного условия для бинарного поиска, и это полностью зависит от того, что означают ваши два предела. Позвольте мне объяснить мой, который, я думаю, довольно прост для понимания, и он позволяет вам модифицировать его для других случаев, не слишком задумываясь.
Назовем два пределаПервым ипоследним . Мы хотим найти первый элемент, больший некоторого x . Следующий инвариант будет держаться все время:
Обратите внимание, что инвариант ничего не говорит об интервале [[5]]., Последний ]. Единственная допустимая инициализация пределов без дальнейшего знания вектора - это первая = 0 и Последняя = последняя позиция вектора. Это удовлетворяет условию, так как нет ничего после последнего и ничего до первого , так что все правильно.Каждый элемент прошедший Последний больше x и каждый элемент до Первый меньше или равен (противоположный случай).
Как интервал [Первый, Последний ] Неизвестен, нам придется продолжать, пока он не опустеет, обновляя границы в последствии.
Как вы можете видеть, нам нужны только два случая, поэтому код очень прост. При каждой проверке мы обновляем границы, чтобы всегда сохранять наш инвариант истинным.int get_first_greater(const std::vector<int>& v, int x) { int first = 0, last = int(v.size()) - 1; while (first <= last) { int mid = (first + last) / 2; if (v[mid] > x) last = mid - 1; else first = mid + 1; } return last + 1 == v.size() ? -1 : last + 1; }Когда цикл заканчивается, используя инвариант, мы знаем, что last + 1 больше x , если он существует, поэтому мы должны только проверить, находимся ли мы все еще внутри нашего вектора или нет.
Имея это в виду, вы можете изменить двоичный поиск, как вы хотите. Давайте изменим его, чтобы найти последнее меньше, чем x . Меняем инвариант:
Каждый элемент перед Первым меньше x и каждый элемент после Последний больше или равен x.
С этим, изменение кода действительно легко:
int get_last_smaller(const std::vector<int>& v, int x) { int first = 0, last = int(v.size()) - 1; while (first <= last) { int mid = (first + last) / 2; if (v[mid] >= x) last = mid - 1; else first = mid + 1; } return first - 1 < 0 ? -1 : first - 1; }Проверьте, что мы только изменили оператор (>= вместо>) и возврат, используя тот же аргумент, что и раньше.
Трудно писать правильные программы. И после того, как программа была проверена на правильность, ее следует редко изменять и чаще использовать повторно. В этой строке, учитывая, что вы используете C++, а не C, я бы посоветовал вам использовать библиотеки std C++ в максимально возможной степени. Обе функции, которые вы ищете, даны вам внутри алгоритм.
Http://en.cppreference.com/w/cpp/algorithm/lower_bound http://en.cppreference.com/w/cpp/algorithm/upper_bound делает волшебство для вас, и, учитывая удивительную силу шаблонов, вы должны быть в состоянии использовать эти методы, просто добавив другие методы, которые реализуют порядок.
HTH.
Чтобы частично ответить на этот вопрос, можно было бы разложить фактическое сравнение (используя функцию обратного вызова или аналогичную), в зависимости от того, будет ли первый элемент, который больше, чем элемент, подлежать поиску, или первый элемент, который меньше. Однако в первом блоке кода Вы используете
arr[mid] <= val && arr[mid+1] > valВ то время как во втором блоке происходит сдвиг индекса во втором условии
if (arr[mid] >= val && arr[mid] < val)Опущено, что кажется непоследовательным.
В ваших процедурах поиска были некоторые ошибки [одна была полностью сломана]. Я их немного почистил, но начал с вашего кода. Примечание: никаких гарантий-здесь уже поздно, но это должно дать вам отправную точку. Обратите внимание на "Ло/привет" является стандартной номенклатуры (например, Ло-это ваш старт и привет тебе конец). Кроме того, обратите внимание, что hi / lo устанавливается в mid и не mid+1 или mid-1
Есть крайние случаи, с которыми нужно бороться. Цикл while должен быть "
int binarysearch_larger(const int *arr,int cnt,int val) // arr -- array to search // cnt -- number of elements in array // val -- desired value to be searched for { int mid; int lo; int hi; int match; lo = 0; hi = cnt - 1; match = -1; while (lo < hi) { mid = (hi + lo) / 2; if (arr[mid] <= val) && (arr[mid+1] > val)) { if ((mid + 1) < cnt) match = mid + 1; break; } if (arr[mid] > val) hi = mid; else lo = mid; } return match; } int binarysearch_smaller(const int *arr,int cnt,int val) // arr -- array to search // cnt -- number of elements in array // val -- desired value to be searched for { int mid; int lo; int hi; int match; lo = 0; hi = cnt - 1; match = -1; while (lo < hi) { mid = (hi + lo) / 2; if (arr[mid] <= val) && (arr[mid+1] > val)) { match = mid; break; } if (arr[mid] > val) hi = mid; else lo = mid; } // the condition here could be "<=" or "<" as you prefer if ((match < 0) && (arr[cnt - 1] <= val)) match = cnt - 1; return match; }
Ниже приведен общий алгоритм, который задал сортированный диапазон элементов и значение, он возвращает пару итераторов, где значение первого итератора является первым элементом в сортированном диапазоне, который сравнивает меньше, чем введенное значение, а значение второго итератора является первым элементом в этом диапазоне, который сравнивает больше, чем введенное значение.
Если пара возвращенных итераторов указывает на конец диапазона, это означает, что введенный диапазон был пуст.
У меня есть сделал его настолько общим, насколько мог, и он также обрабатывает маргинальные случаи и дубликаты.
template<typename BidirectionalIterator> std::pair<BidirectionalIterator, BidirectionalIterator> lowhigh(BidirectionalIterator first, BidirectionalIterator last, typename std::iterator_traits<BidirectionalIterator>::value_type const &val) { if(first != last) { auto low = std::lower_bound(first, last, val); if(low == last) { --last; return std::make_pair(last, last); } else if(low == first) { if(first != last - 1) { return std::make_pair(first, std::upper_bound(low, last - 1, val) + 1); } else { return std::make_pair(first, first); } } else { auto up = std::upper_bound(low, last, val); return (up == last)? std::make_pair(low - 1, up - 1) : std::make_pair(low - 1, up); } } return std::make_pair(last, last); }ЖИВАЯ ДЕМОНСТРАЦИЯ