Member 13435651 Ответов: 2

Как мне ... написать программу для бинарного поиска

Разработайте программу для реализации алгоритма бинарного поиска. Этот метод сравнивает значение ключа поиска элемента, который находится на полпути в отсортированном списке. Затем ;
а) если они совпадают, поиск окончен.
(Б) если значение ключа поиска меньше среднего значения, то первая половина списка содержит значение ключа.
(в) если значение ключа поиска больше среднего значения, то вторая половина содержит значение ключа.
Повторяйте эту стратегию "разделяй и властвуй", пока у нас не будет совпадения. Если список сокращен до одного несоответствующего элемента, то список не содержит значения ключа.

ТЕСТ 1
ВХОД

10 11 12 13 1 3 2 4 7 8 110 122 123
2
ВЫХОД


Элемент находится в списке, и его позиция равна=7

Что я уже пробовал:

#include <stdio.h>
main()
{
int top,bottom,middle,value[50],key,n,i;
clrscr();
printf("Enter the number of elements in array:");
scanf("%d",&n);
printf("Enter the elements of array in ascending order\n");
for(i=1;i<=n;i++)
scanf("%d",&value[i]);
printf("Enter the value which you want to search:");
scanf("%d",&key);
top=n-1;
bottom=0;
do
{
middle=(top+bottom)/2;
if(value[middle]<key)
bottom=middle+1;
else
top=middle;
}
while(top>bottom);
if(top==-1)
printf("List is empty!");
else if(value[top]==key)
printf("value has been found!");
else
printf("Target value has not been found!");
getch();

	return 0;
}

OriginalGriff

И что же?
Что он делает такого, чего вы не ожидали, или не делает того, что вы сделали?
Какая помощь вам нужна?

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

jeron1

ВХОД
10 11 12 13 1 3 2 4 7 8 110 122 123
2
ВЫХОД
Элемент находится в списке, и его позиция равна=7

таким образом, элементы не вводятся по возрастанию
приказ?

Richard MacCutchan

Сначала вам нужно отсортировать входные элементы, чтобы выполнить правильный двоичный поиск.

2 Ответов

Рейтинг:
0

CPallini

Хорошая новость: реализация выглядит правильной. Ну, есть небольшой недостаток, на мой взгляд:

Цитата:
для(i=1;i<=n; i++)
следует
for(i=0;i<n;i++)



Кроме того, вероятно, было бы лучше сообщить о положении найденного элемента, т. е. заменить
Цитата:
printf ("значение найдено!");
с
printf("value has been found at position %d", (top+1));


Плохая новость: тестовый случай совершенно неправильный (число должно быть в порядке возрастания).

Рейтинг:
0

Patrice T

Совет: начните с правильного отступа вашего кода, он показывает структуру и помогает читать.
Профессиональные редакторы программистов имеют такую функцию наряду с другими полезными для программистов.
Notepad++ Home[^]
UltraEdit | Оригинальный Текстовый Редактор[^]

#include <stdio.h>
main()
{
    int top,bottom,middle,value[50],key,n,i;
    clrscr();
    printf("Enter the number of elements in array:");
    scanf("%d",&n);
    printf("Enter the elements of array in ascending order\n");
    for(i=1;i<=n;i++)
        scanf("%d",&value[i]);
    printf("Enter the value which you want to search:");
    scanf("%d",&key);
    top=n-1;
    bottom=0;
    do
    {
        middle=(top+bottom)/2;
        if(value[middle]<key)
            bottom=middle+1;
        else
            top=middle;
    }
    while(top>bottom);
        if(top==-1)
            printf("List is empty!");
        else if(value[top]==key)
            printf("value has been found!");
        else
            printf("Target value has not been found!");
    getch();

    return 0;
}

Дихотомический поиск-Википедия[^]
-----
Существует инструмент, который позволяет вам видеть, что делает ваш код, его имя отладчик Это также отличный инструмент обучения, потому что он показывает вам реальность, и вы можете увидеть, какие ожидания соответствуют реальности.
Когда вы не понимаете, что делает ваш код или почему он делает то, что делает, ответ таков: отладчик.
Используйте отладчик, чтобы увидеть, что делает ваш код. Просто установите точку останова и посмотрите, как работает ваш код, отладчик позволит вам выполнять строки 1 на 1 и проверять переменные по мере их выполнения.

Отладчик-Википедия, свободная энциклопедия[^]

Освоение отладки в Visual Studio 2010 - руководство для начинающих[^]
Базовая отладка с помощью Visual Studio 2010-YouTube[^]
Отладчик здесь для того, чтобы показать вам, что делает ваш код, и ваша задача-сравнить его с тем, что он должен делать.
В отладчике нет никакой магии, он не находит ошибок, он просто помогает вам. Когда код не делает того, что ожидается, вы близки к ошибке.