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

@ProFrog111 · Регистрация: 08.10.2015

Студворк — интернет-сервис помощи студентам

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

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <iostream>
#include <cstdlib>
using namespace std;
//сортировка вставкой по убыванию
void insertSort(int *arrayPtr, int length);
// бинарный поиск числа
void binnary(int*sorted_array );
 
 
int main( )
{
    cout << "Введите размер массива: ";
    int size_array; // длинна массива
    cin >> size_array;
 
    int *sorted_array = new int [size_array]; //  динамический массив
    cout<<endl;   
    cout<<"Одномерный массив:";
    for (int counter = 0; counter < size_array; counter++) // цикл заполнения массива
    {
 
        sorted_array[counter] = rand() % 100; // заполняем массив случайными числами
        cout <<sorted_array[counter] << "  "; // вывод массива на экран
    }
    cout << endl;
 
    insertSort(sorted_array, size_array); // вызов функции сортировки вставками
    cout<<"Отсортиров массив:"; 
    for (int counter = 0; counter < size_array; counter++)
    {
        cout <<sorted_array[counter] << "  "; // печать отсортированного массива
    }
    
    binnary(sorted_array);
     cout<<endl;
    
    
    delete [ ] sorted_array; // высвобождаем память
    system("pause");
    return 0;
}
 
 
void insertSort(int *arrayPtr, int length) // сортировка вставками
{
    int temp, // переменная для хранения значения элемента сортируемого массива
        item; // индекс предыдущего элемента
    for (int counter = 1; counter < length; counter++)
    {
        temp = arrayPtr[counter]; // инициализируем временную переменную текущим значением элемента массива
        item = counter-1; // запоминаем индекс предыдущего элемента массива
        while(item >= 0 && arrayPtr[item] < temp) // пока индекс не равен 0 и предыдущий элемент массива больше текущего
        {
            arrayPtr[item + 1] = arrayPtr[item]; // перестановка элементов массива
            arrayPtr[item] = temp;
            item--;
        }
    }
}
 
 
 
 
void binnary(int*sorted_array )
{
   int
         average_index, // хранение среднего элемента
         first_index, // хранение первого элемента
         last_index;  // хранение последнего элемента 
int search;
cin>>search;
// искомое число
  // if( last_index == -1)
   //    cout<<"Массив пуст!"<<endl;
bool f=false;
   while  ((first_index<=last_index)&&(!f))
{
       average_index = (first_index+last_index )/2; 
       // проверяем найден ли будет элемент (выражение)?(если верно):(если ложно)
  
  if (search == sorted_array[average_index])
{
 f=true;
}  
else    
   if  (search > sorted_array[average_index])
{
    last_index  = average_index-1;
    }  
else  
   if  (search < sorted_array[average_index])
{
    first_index  = average_index+1;
    }
}   
if (f) cout<<"Искомое число:"<< sorted_array[average_index]<<endl;
else
cout<<"Введенное число не найдено";
}

@shilko2013 · 02.11.2016, 08:22

Скопируйте из реализации binarysearch алгоритма STL ��

@ProFrog111 · 08.11.2016, 01:21 **[ТС]**

Может кому нужен будет(писал через Ideone "c++14") все работает корректно, только нужно добавить кому нужно проверку на неповторяемость случайных чисел в массиве

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <iostream>
using namespace std;
int Search_Binary (int arr[], int left, int right, int key) ;
void insertSort(int *arrayPtr, int length);
// функция с алгоритмом двоичного поиска 
int Search_Binary (int array[], int left, int right, int key)
{
    int midd = 0;
    while (1)
    {
        midd = (left + right) / 2;
 
        if (key < array[midd])       // если искомое меньше значения в ячейке
            right = midd - 1;      // смещаем правую границу поиска
        else if (key > array[midd])  // если искомое больше значения в ячейке
            left = midd + 1;       // смещаем левую границу поиска
        else                       // иначе (значения равны)
            return midd;           // функция возвращает индекс ячейки
 
        if (left > right)          // если границы сомкнулись 
            return -1;
    }
}
 
 
 
void insertSort(int *arrayPtr, int length) // сортировка вставками
{
    int temp, // переменная для хранения значения элемента сортируемого массива
        item; // индекс предыдущего элемента
    for (int counter = 1; counter < length; counter++)
    {
        temp = arrayPtr[counter]; // инициализируем временную переменную текущим значением элемента массива
        item = counter-1; // запоминаем индекс предыдущего элемента массива
        while(item >= 0 && arrayPtr[item] < temp) // пока индекс не равен 0 и предыдущий элемент массива больше текущего
        {
            arrayPtr[item + 1] = arrayPtr[item]; // перестановка элементов массива
            arrayPtr[item] = temp;
            item--;
        }
    }
}
 
 
 
 
 
int main()
{   
 srand(time(NULL)); 
 int SIZE;
cout<<"Введите размер массива:"<<endl;
cin>>SIZE;
    int *array= new int [SIZE];
for(int counter=0; counter<SIZE; counter++ )
{
   array[counter] = rand() % 100; // заполняем массив случайными числами
   cout <<array[counter] << " | "; // вывод массива на экран
}
    int key = 0;
    int index = 0; // индекс ячейки с искомым значением
 
    insertSort(array, SIZE); // вызов функции сортировки вставками
    cout<<endl;
    cout<<"Отсортиров массив:"; 
    cout<<endl;
 
    for (int counter = 0; counter < SIZE; counter++)
    {
        cout<<array[counter] << " | "; // печать отсортированного массива
    }
    cout<<endl;
    cout << "Введите любое число: ";
    cin >> key;
 
 
    index = Search_Binary (array, 0, SIZE, key);
 
    if (index >= 0) 
        cout << "Указанное число находится в ячейке с индексом: " << index << "\n\n";
    else
        cout << "В массиве нет такого числа!\n\n";
 
    return 0;
}

Добавлено через 22 часа 41 минуту
Ошибочка, вот работающий код...

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <iostream>
using namespace std;
    int midd;
int Search_Binary (int arr[], int left, int right, int key) ;
void insertSort(int *arrayPtr, int length);
// функция с алгоритмом двоичного поиска 
int Search_Binary (int array[] ,  int key, int SIZE)
{
    bool flag=false;
 
    int left=0; 
    int right=SIZE-1;
    while ((left<=right) && (!flag))
    {
        midd = (left + right) / 2;
 
        if (key > array[midd])       // если искомое меньше значения в ячейке
 
            right = midd - 1; // смещаем правую границу поиска
 
        else if (key < array[midd])  // если искомое больше значения в ячейке
 
            left = midd + 1;    // смещаем левую границу поиска
 
        else                       // иначе (значения равны)
             flag=true;
 
    }
    return flag;
}
 
 
void insertSort(int *arrayPtr, int length) // сортировка вставками
{
    int temp, // переменная для хранения значения элемента сортируемого массива
        item; // индекс предыдущего элемента
    for (int counter = 1; counter < length; counter++)
    {
        temp = arrayPtr[counter]; // инициализируем временную переменную текущим значением элемента массива
        item = counter-1; // запоминаем индекс предыдущего элемента массива
        while(item >= 0 && arrayPtr[item] < temp) // пока индекс не равен 0 и предыдущий элемент массива больше текущего
        {
            arrayPtr[item + 1] = arrayPtr[item]; // перестановка элементов массива
            arrayPtr[item] = temp;
            item--;
        }
    }
}
 
int main()
{   
const int SIZE=5;
cout<<"Введите эллементы массива:"<<endl;
int array[SIZE];
for(int counter=0; counter<SIZE; ++counter )
{
cin>>array[counter];
cout<<array[counter]<<" | ";    
}
 
 
 
    int key ;
    int index; // индекс ячейки с искомым значением
 
    insertSort(array, SIZE); // вызов функции сортировки вставками
    cout<<endl;
    cout<<"Отсортиров массив:"; 
    cout<<endl;
 
    for (int counter = 0; counter < SIZE; counter++)
    {
        cout<<array[counter] << " | "; // печать отсортированного массива
    }
 
    cout<<endl;
    cout << "Введите любое число: ";
    cin >> key;
 
//  index = Search_Binary (array,key,SIZE,-1);
 
    if (Search_Binary (array,key,SIZE)) 
        cout << "Указанное число находится в ячейке с индексом: " << midd << "\n\n";
    else
        cout << "В массиве нет такого числа!\n\n";
 
    return 0;
}

@zarko97 · 26.02.2017, 20:27

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
template<class Iter, class Key, class Func>
std::pair<Key, std::ptrdiff_t> binary_search(Iter beg, Iter end, Key key, Func func)
{
    if (beg == end)
        return std::make_pair(-1, -1);
    auto pivot = beg;
    std::advance(pivot, std::distance(pivot, end) / 2);
    if (*pivot == key)
        return std::make_pair(key, std::distance(beg, pivot));
    if (*pivot > key)
        return binary_search(beg, pivot, key);
    return binary_search(++pivot, end, key);
}

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@shilko2013 257 / 234 / 185 Регистрация: 02.04.2016 Сообщений: 898
	02.11.2016, 08:22
	Скопируйте из реализации binarysearch алгоритма STL �� 0