Как добавить элемент c в отсортированный вектор без использования стандартных алгоритмов?

Question

Мой код не работает в некоторых случаях: когда c1 равен 4, он ничего не выводит, но работает для чисел больше 9. Почему это так?

#include<iostream>
#include<vector>
using namespace std;
void insertfast(vector<int>&v, int c)
{
if (c >= v[v.size()-1])v.push_back(c);
if (c <= v[0])v.insert(v.begin(), c);
int min = 1;
int max = v.size();
while (v.size() != 9) {
    int i = (min + max) / 2;
    if (v[i - 1] <= c && c <= v[i])v.insert(v.begin() + i, c);
    if (v[i] <= c && c <= v[i + 1])v.insert(v.begin() + (i + 1), c);
    if (c < v[i])
        max = i;
    else
        min = i;
}
}
int main()
{
vector<int>v1 = { 2,5,9,22,44,55,88,777 };
int c1 = 4;

insertfast(v1, c1);

for (int i = 0; i < 9; i++)
    cout << v1[i] << endl;
}

Answer 1

Давайте потратим секунду, чтобы логически пройтись по коду здесь, так как я предполагаю, что это домашнее задание, важно понять, как это сделать. Существуют такие инструменты, как отладчики, которые используются в более крупных проектах и ​​для более сложных задач, но небольшие логические ошибки, подобные этой, случаются постоянно.

Хорошо, поэтому insertfast() - это функция для вставки int в vector<int> упорядоченным образом. Первое, что вы делаете, сравниваете первый и последний элементы вектора.

if (c >= v[v.size() - 1]) 
    v.push_back(c); 
if (c <= v[0]) 
    v.insert(v.begin(), c);

Мы можем быть только одной из этих вещей, и если они верны, мы закончили. Так что лучший вариант здесь - просто return из функции, нам больше не нужно ничего делать. Мы знаем это, но программа не знает. Он будет продолжать сравнивать вещи, которые мы не хотим сравнивать и выдавать ошибки.

if (c >= v[v.size() - 1]) {
    v.push_back(c);
    return;
}
if (c <= v[0]) {
    v.insert(v.begin(), c);
    return;
}

Что если оба эти утверждения ложны, и мы все еще в функции? Нам все еще нужно выяснить, куда вставить это значение, поэтому мы перебираем элементы.

while (v.size() != 9)

Это очень плохой условный цикл, так как он будет только работать, если мы передадим в функцию вектор размера 8. С вашей конкретной арифметикой вы, по сути, хотите цикл, пока какое-либо значение не будет добавлено к вектору. Я рекомендую безусловный цикл (в конце концов, мы пытаемся быть "быстрым"), то есть бесконечный цикл, и явно возвращаем или перерыв в цикле.

int min = 1;
int max = v.size();
while (1) {
    int i = (min + max) / 2;
    if (v[i - 1] <= c && c <= v[i]) {
        v.insert(v.begin() + i, c);
        return;
    }
    if (v[i] <= c && c <= v[i + 1]) {
        v.insert(v.begin() + (i + 1), c);
        return;
    }
    if (c < v[i])
        max = i;
    else
        min = i;
}

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

Answer 2

В вашем коде две логические проблемы:

1. Для ваших тестовых данных в функции insertfast() вы входите в while(), когда вы входите в первое if (v[i - 1] <= c && c <= v[i]), вы вставляете значение 4 и в становится v[1], и у вас есть шаг сразу после этого в следующий if (v[i] <= c && c <= v[i + 1]), поэтому вам нужно установить секунду, если else if, например:

   if (v[i - 1] <= c && c <= v[i])
   {
       v.insert(v.begin() + i, c);
   }
   else if (v[i] <= c && c <= v[i + 1])
   {
       v.insert(v.begin() + (i + 1), c);
   }
   

2. Из предыдущего элемента ваш вектор увеличился на 2 элемента, поэтому его размер становится 10, а у вас бесконечный цикл while (v.size() != 9), я думаю, что вы можете просто сделать break, чтобы выйти из цикла в случае успеха вставить:

   if (v[i - 1] <= c && c <= v[i])
   {
       v.insert(v.begin() + i, c);
       break;
   }
   else if (v[i] <= c && c <= v[i + 1])
   {
       v.insert(v.begin() + (i + 1), c);
       break;
   }
   

Нет необходимости запускать цикл дальше, если вы вставили элемент. На самом деле 2-й элемент с break исправит и else пропустит проблему, в случае вставки он выйдет из цикла и не сможет перейти в секунду, если.