Двоичный поиск не работает для определенного выхода - PullRequest
Новая
       6

Двоичный поиск не работает для определенного выхода

0 голосов
/ 05 октября 2019

Получение неожиданного вывода только для одного входа в двоичном поиске. Когда я ввожу {1,2,3,4,5} в качестве ввода в массив в программе бинарного поиска, он показывает, что элемент отсутствует только для ввода '2 ', даже если элемент присутствует. Попытка кодовых блоков.

Я пытался отслеживать код в итерации, и я не понимаю, почему это не работает, и если значение переменной (pos - это мой случай) меняется или нет. 

#include <iostream>
using namespace std;

int main()
{
    int last,fin,beg=0,mid,pos=-1,i,*a;

    cout<<"Enter the size of array: ";
    cin>>last;

    a=new int[last];

    cout<<"Enter the elements in array"<<endl;
    for(i=0;i<last;i++)
    {
        cin>>a[i];                            
    }

    cout<<endl<<"Enter the element you want to find: ";
    cin>>fin;

    for(i=beg;i<=last;i++)
    {

        mid=(beg+last)/2;

        if(a[mid]==fin)
        {
            pos=mid;
        }
        else if(a[mid]>fin)
        {
            last=mid-1;
        }
        else
        {
            beg=mid+1;
        }
    }

    if(pos==-1)
    {
        cout<<"Element not present in array"<<endl;
    }
    else
    {
        cout<<"element found "<<fin<<" at "<<pos+1<<" position"<<endl;
    }

    delete a;
    return 0;
}

Я ожидаю, что вывод 2 должен быть: элемент найден 2 в позиции 2, когда я введу размер (переменная last) как 5 и элементы как 1,2,3,4,5. Я получаю вывод: Элемент отсутствует в массиве.

1 Ответ

0 голосов
/ 05 октября 2019

Измените ваш цикл следующим образом: 

while (beg <= last) {
    int mid = (beg + last) / 2;
    if (a[mid] == fin) {
        pos = mid;
        break;              // break where you find the element in the array
    }
    else if (a[mid] > fin) last = mid - 1;
    else beg = mid + 1;
}

Ваш цикл неверен. Вы изменяете границы для поиска в цикле (beg и last). Таким образом, чтобы проверить, не можете ли вы продолжить поиск, вам нужно проверить, пересекает ли beg last, и в этом случае вы прекратите поиск.

Кроме того, в вашем коде a - это массив, выделенный с помощью new, но вы вызываете delete a вместо delete[] a.

...