Хотите найти минимальный и максимальный индекс в векторе с помощью BinarySearch

#c #c 14 #binary-search

#c #c 14 #двоичный поиск

Вопрос:

Я только что узнал, как работает двоичный поиск, и мне нужно найти минимальный и максимальный индекс в векторе. Я пробовал несколько вещей, но каждый раз, когда моя функция избегает части моего кода… У меня больше нет идей, это не кажется таким уж сложным, но все же… Я много борюсь с этой концепцией.

РЕДАКТИРОВАТЬ: я понимаю, что мое объяснение не существовало. Итак, что я хочу сделать, так это для данной ноты я хочу найти наименьший ее индекс в векторе элементов песни.

вот моя ближайшая попытка :

   int Song::binarySearchMin(const Noteamp; note)
{
int Min = 0, Max = notes.size() ,ind=0;
    while (Min <= Max)
    {
        int middle = (Min   Max) / 2;
        if (note == notes[middle])
        {
            ind = middle;
            Max = middle;
            while (Min <= Max)
            {
                middle = (Min   Max) / 2;
                if ((note == notes[middle]) amp;amp; (middle <= ind))
                {
                    ind = middle;
                }
                Max = middle - 1;
            }
            return ind;
        }
        else if (note < notes[middle])
        {
            Max = middle-1;
        }
        else
        {
            Min = middle  1;
        }
    }
    return -1;
}

Я не могу понять, почему он не охватывает каждую ситуацию. Прямо сейчас это работает, когда мой индекс находится посередине. Но он не может обрабатывать несколько индексов.

1. Используйте английские имена для вашей переменной, которые помогут не-французскому сообществу понять их использование 😉

2. О, действительно, спасибо, что это сделано.

3. Если вы хотите использовать двоичный поиск, вам нужно отсортировать данные … но если вы сортируете по данным, вам больше не нужно искать минимальные и максимальные значения… для линейного поиска просто используйте std::minmax_element .

4. Является ли песня набором нот? В таком случае отсортирован ли массив заметок? Звучит как ужасная песня 🙂

5. Хорошо … итак, подумайте об этом еще раз … если данные отсортированы, нужен ли вам поиск, чтобы найти минимальное и максимальное значение. Подумайте очень хорошо! Будут ли они (всегда) находиться на месте? (P.s. вам нужно добавить @ перед моим именем, чтобы пометить меня)

Ответ №1:

насколько я знаю, двоичный поиск работает с отсортированными данными, поэтому я думаю, что не стоит использовать его для несортированных данных, поиск min и max в несортированном векторе требует линейного поиска. и двоичный поиск эффективен при поиске элемента в отсортированном массиве или векторе.

1. Да, вы правы. Наше упражнение предназначено только для того, чтобы мы поняли все, что касается сложности / сортировки и двоичного поиска. Поэтому нам пришлось создать отсортированную область для этого конкретного вопроса