Реализация бинарного поиска

@uLong · Регистрация: 18.04.2015

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

Здравствуйте. Решил реализовать на С++ бинарный поиск. Вместо массива я взял vector (думаю особой роли это не играет), все бы хорошо, НО. Мой вариант не находит числа, если их в массиве 2 или больше.
Пример: "1, 2, 3, 4, 4, 7, 15, 124" — Поиск не найдет число "4". Хочу знать где моя ошибка, ибо у меня не получается (неопытность мешает) найти её.
Моя реализация бинарного поиска:

C++

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
bool binary_search(vector<int> &a,int x, int l, int r) 
{
    while (r - l > 1)
    {
        int mid = (l + r) / 2;
 
        if (a[mid] < x)
            l = mid;
        else
            r = mid;
    }
 
    for (auto i = a.begin(); i != a.end(); i++)
        if (*i == x)
            return true;
        else
            return false;
}
 
int main()
{
    vector<int>a = { 1, 4, 2, 6, 10, 4, 2, 100, 34, 12 };
    int b = 0;
    sort(a.begin(), a.end());
    
    cout << "Array: ";
    for (auto &c : a)
        cout << c << " ";
    cout << endl;
    cout << "Search: ";
    cin >> b;
 
    cout << binary_search(a, b, 0, a.size() - 1);
 
    while (true);
    return 0;
}

@daslex · 13.06.2015, 14:37

C++

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
bool binary_search(vector<int> &a,int x, int l, int r)
{
    int mid;
    while (r - l > 1)
    {
         mid = (l + r) / 2;
 
        if (a[mid] < x)
            l = mid;
        else
            r = mid;
    }
 
    return !(a[mid]-x);
 
}
 
int main()
{
    vector<int> a = { 1, 4, 2, 6, 10, 4, 2, 100, 34, 12 };
    int b = 0;
    sort(a.begin(), a.end());
 
    cout << "Array: ";
    for (auto &c : a)  cout << c << " ";
    cout << endl;
 
    cout << "Search: ";
    cin >> b;
 
   
    cout << binary_search(a, b, 0, a.size() );
 
 
    return 0;
}

Добавлено через 4 минуты

Сообщение от uLong

for (auto i = a.begin(); i != a.end(); i++)

стр 19 вообще непонятно что. Это обычный линейный поиск, ведь массив не изменялся.

стр 11
Объявленная внутри цикла переменная, внутри цикла и умрет.

@uLong · 13.06.2015, 14:55 **[ТС]**

Сообщение от daslex

C++

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
bool binary_search(vector<int> &a,int x, int l, int r)
{
    int mid;
    while (r - l > 1)
    {
         mid = (l + r) / 2;
 
        if (a[mid] < x)
            l = mid;
        else
            r = mid;
    }
 
    return !(a[mid]-x);
 
}
 
int main()
{
    vector<int> a = { 1, 4, 2, 6, 10, 4, 2, 100, 34, 12 };
    int b = 0;
    sort(a.begin(), a.end());
 
    cout << "Array: ";
    for (auto &c : a)  cout << c << " ";
    cout << endl;
 
    cout << "Search: ";
    cin >> b;
 
   
    cout << binary_search(a, b, 0, a.size() );
 
 
    return 0;
}

Добавлено через 4 минуты

стр 19 вообще непонятно что. Это обычный линейный поиск, ведь массив не изменялся.

стр 11
Объявленная внутри цикла переменная, внутри цикла и умрет.

Спасибо. Можете пояснить следующий код ?

Сообщение от daslex

return !(a[mid]-x);

Я вообще новичек, просто изучаю простые алгоритмы. Вы написали все одной строчкой, когда на сайтах с примерами там целый цикл, объясните, пожалуйста.

@daslex · 13.06.2015, 15:20

Сообщение от uLong

return !(a[mid]-x);

Это сокращенная запись

C++

1
2

if (a[mid] - x == 0) return true;  //ЕСли элемент был найден, то вычитание одинаковых значений даст ноль
else return false;//Если последний элемент не равен тому, который искали, то вычитание разных значений, а значит не ноль

! - логическое отрицание. Инвертирование.

Не по теме:

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

Новые блоги и статьи
[Golang] 121. Best Time to Buy and Sell Stock alhaos 28.01.2025 В этой задаче мы получаем слайс целых чисел, которые означают цену акции в разные моменты времени, и должны вернуть максимально возможную прибыль от купли продажи акции. / / . . .	Проектирование и моделирование hw_wired 28.01.2025 Введение в моделирование Моделирование представляет собой один из фундаментальных методов научного познания, который позволяет изучать объекты и явления через создание их упрощенных аналогов. В. . .	Алгоритмы и исполнители hw_wired 28.01.2025 Введение в алгоритмы В современном мире информационных технологий алгоритмы играют основополагающую роль в решении различных задач и автоматизации процессов. Алгоритм представляет собой точную. . .	Хранение информации hw_wired 28.01.2025 Введение: Роль систем хранения информации в современном мире В современную эпоху цифровых технологий эффективное хранение информации становится одним из ключевых факторов успешного развития любой. . .	Обработка числовой информации hw_wired 28.01.2025 Введение в обработку числовой информации В современном мире обработка числовой информации стала неотъемлемой частью как профессиональной деятельности, так и повседневной жизни. Электронные таблицы. . .	Мультимедиа hw_wired 28.01.2025 Введение в мультимедийные технологии В современном мире мультимедийные технологии стали неотъемлемой частью нашей жизни, проникнув во все сферы человеческой деятельности. Термин "мультимедиа". . .
Обработка текстовой информации hw_wired 28.01.2025 Введение в обработку текстовой информации В современном мире обработка текстовой информации играет фундаментальную роль в различных сферах человеческой деятельности. Текстовые редакторы стали. . .	Обработка графической информации hw_wired 28.01.2025 Введение в компьютерную графику Компьютерная графика стала неотъемлемой частью современного цифрового мира, пройдя впечатляющий путь развития от простейших черно-белых изображений до сложных. . .	Python в Алгоритмике: Решение задач hw_wired 28.01.2025 Введение в Python и Алгоритмику В современном мире программирование стало неотъемлемой частью образования и профессионального развития. Python зарекомендовал себя как один из самых популярных и. . .	Компьютер как универсальное устройство для работы с информацией hw_wired 28.01.2025 Введение в устройство компьютера Компьютер представляет собой универсальное электронное устройство, предназначенное для автоматической обработки информации. В современном мире компьютер стал. . .	Информация и информационные процессы hw_wired 28.01.2025 Понятие информации и ее виды В современном мире информация является одним из фундаментальных понятий, пронизывающих все сферы человеческой деятельности. Под информацией понимают любые сведения об. . .	Алгоритмика hw_wired 28.01.2025 Введение: Основы алгоритмики и её роль в информатике В современном мире программирование и алгоритмическое мышление стали неотъемлемой частью образования и профессиональной деятельности. . . .

	13.06.2015, 15:20