1 / 1 / 0
Регистрация: 14.11.2014
Сообщений: 47
1

Бинарный поиск элемента в массиве

10.12.2015, 23:03. Показов 3337. Ответов 4
Метки нет (Все метки)

Суть - программа ищет число по формуле K=(a+b)/2 бинарным поиском, и выводит его порядковый номер (индекс) в отсортированом массиве. Проблема заключается в том что программа считает число по формуле, генерирует массив, но в итоге пишет "Element not found" хотя число в массиве присутствует
Бинарный поиск элемента в массиве


Кликните здесь для просмотра всего текста

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <windows.h>
#include <iostream>
#include <time.h>
 
using namespace std;
int n;
int BinarySearch (int A[], int key)
{
    int left=0, right=n, mid;
    while (left<=right)
    {
        mid=left+(right-left)/2;
        if(key<A[mid])right=mid-1;
        else if(key>A[mid])left=mid+1;
        else return mid;
    }
    return -1;
}
void bubbleSort(int*P,int n)
{
    int i=0,pass,hold;
    for (pass=1; pass<=n; pass++)
        for(i=0;i<=n-2;i++)
        if(P[i]<P[i+1])
    {
        hold= P[i];
        P[i]=P[i+1];
        P[i+1]=hold;
    }
}
int main()
{
    int a,b;
    srand (4);
    cout<<"Range A B"<<endl;
    cin>>a>>b;
    int i,key=((a+b)/2.0),A[1000];
    cout<<"Size>";cin>>n;
    cout<<"Element>"<<key<<endl;
    cout<<"Start massive: ";
    for (i=0; i<n-1; i++)
    {
        A[i]=a+rand()%(b-a+1);
        cout<<A[i]<<" ";
    }
A[i]=a+rand()%(b-a+1);
cout<<A[i]<<" ";
{
    bubbleSort(A,n);
    cout<<endl;
    cout<<"End massive: ";
    for (i=0; i<=n-1;i++)cout<<A[i]<<" ";
    if (BinarySearch(A,key)==-1)
        cout<<"\n Element not found";
    else cout<<"\n Element number: "<<BinarySearch(A,key)+1;
    return 0;
}
}
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
10.12.2015, 23:03
Ответы с готовыми решениями:

Реализовать бинарный поиск заданного элемента в массиве
Помогите, напишите бинарный поиск элемента в массиве (особенно чтобы он работал, когда все элементы...

Двоичный (бинарный) поиск элемента в двумерном массиве
Доброго времени суток. есть вот такое задание: Написать функцию, реализующую алгоритм бинарного...

Реализовать бинарный поиск заданного элемента в массиве
Доброго времени суток, форумчане! Реализую алгоритмы поиска: линейный и бинарный. Нужно, чтоб они...

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

4
1386 / 1016 / 323
Регистрация: 28.07.2012
Сообщений: 2,804
10.12.2015, 23:14 2
Цитата Сообщение от DrTeemo Посмотреть сообщение
C++
1
2
if(key<A[mid])right=mid-1; 
else if(key>A[mid])left=mid+1;
Твой "пузырёк" сортирует массив по убыванию,
так что если искомый элемент меньше элемента по середине,
то нужно сдвигать левую границу, если больше - правую.
1
1 / 1 / 0
Регистрация: 14.11.2014
Сообщений: 47
10.12.2015, 23:39  [ТС] 3
Или я не понял (что скорее всего) или что-то не так делаю, теперь пишет что элемент 8-ой (61)
0
1386 / 1016 / 323
Регистрация: 28.07.2012
Сообщений: 2,804
11.12.2015, 00:00 4
Лучший ответ Сообщение было отмечено DrTeemo как решение

Решение

Цитата Сообщение от DrTeemo Посмотреть сообщение
Или я не понял (что скорее всего)
Нужно было в двух вышеперечисленных строках поменять left=... и right=... местами.
Цитата Сообщение от DrTeemo Посмотреть сообщение
right=n
right=n-1
1
1 / 1 / 0
Регистрация: 14.11.2014
Сообщений: 47
11.12.2015, 00:11  [ТС] 5
Ясно, спасибо Вам большое!)
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
11.12.2015, 00:11
Помогаю со студенческими работами здесь

Бинарный поиск в массиве
Нужно написать программу для курсовой по теме : Разработка Windows приложения для бинарного поиска...

Бинарный поиск в массиве с++
Помогите, пожалуйста с задачей: Создать массив из 20-ти елементов, инициализировать массив. 1)...

Бинарный поиск в массиве
Помогите нужна программа по поиску числа в массиве (бинарным методом). Очень очень нужно:(

Бинарный поиск элемента массива
Всем привет. Помогите пожалуйста. Есть массив X из n елементов, который рандомится в диапазоне ....


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2023, CyberForum.ru