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

@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);
}

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .

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