функции линейного/бинарного поиска ничего не отображают?

Я сравниваю линейный и бинарный поиск и скорость, с которой каждый из них это делает. Но когда я компилирую программу, ничего не отображается, и я не могу понять, почему. Это работало, когда я вводил и тестировал только часть линейного поиска. Любая помощь будет принята с благодарностью~~. Спасибо.

#include <iostream>
using namespace std;

int linearSearch(const int integerArray[],int,int);
int binarySearch(const int integerArray[],int,int);
const int SIZE = 20;

    int main()
    {
        int integerArray[SIZE]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,10};
        int position1,position2;

        cout << "This program will compare search efficiency for the linear and binary searches " << endl;

        position1 = linearSearch(integerArray,SIZE,7);
        position2 = binarySearch(integerArray,SIZE,7);

        cout << position1 << endl;
        cout << position2 << endl;

        return 0;
    }

    int linearSearch(const int integerArray[],int SIZE,int value)
    {
        int index = 0;
        int position1 = -1;
        bool foundNum = false;

        while(index < SIZE)
        {
            if(integerArray[index] == value)
            {
                foundNum = true;
                position1 = index;
            }
            index++;
        }
        return position1;
    }

    int binarySearch(const int integerArray[],int size,int value)
    {
        int first = 0;
        int last = size-1;
        int midpoint = (first+last)/2;
        int position2 = -1;
        bool foundNum = false;

        while(!foundNum && first<=last)
        {
            if(integerArray[midpoint] == value)
            {
                foundNum = true;
                position2++;
                return position2;
            }
            else if(integerArray[midpoint] > value)
            {
                last = midpoint-1;
                position2++;
            }
            else
                last = midpoint+1;
                position2++;


        }
        return position2;
    }

person user3063911    schedule 04.12.2013    source источник


Ответы (2)


В вашей функции binarySearch функция midpoint никогда не изменяется, поэтому результатом является бесконечный цикл, если только число не будет найдено мгновенно.

Вы должны обновить midpoint, поместив midpoint = (first+last)/2; внутрь цикла.

person yizzlez    schedule 04.12.2013

Это звучит как домашнее задание, поэтому я не буду делать это за вас, но, похоже, проблема связана с вашим бинарным поиском. Рассмотрим эти предметы:

  1. Повторный расчет средней точки необходимо выполнять каждую итерацию. Вы делаете это только один раз.
  2. Должен быть случай, когда вы изменяете first, и отдельный случай, когда вы изменяете last. У вас есть два случая, которые изменяют last.
  3. Вам вообще нужен position2? Разве переменная midpoint не служит этой цели?

Удачи!

person Matt    schedule 04.12.2013