Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Mikhail1990
22 / 21 / 4
Регистрация: 22.03.2014
Сообщений: 256
#1

Бинарный поиск - C++

02.02.2015, 13:39. Просмотров 614. Ответов 3
Метки нет (Все метки)

Прочитал статью на хабре, о том, что только 10 проц программистов смогут реализовать бин поиск. Раньше никогда с ним не имел дело, прочитав принцип работы, вот что написал.
Товарищи прошу раскритиковать. И дать более оптимальный вариант! Спасибо!

Кликните здесь для просмотра всего текста
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
#include <iostream>
#include <cmath>
#include "vld.h"
 
using namespace std;
 
int main()
{
    const int size=10;
    int mas[size]={0,1,2,3,4,5,6,7,8,9};
    int find_value=5;
    int index=0;
    int count=0;
 
    int pos=size/2;  //ищем среднюю позицию в массиве
 
    if(mas[pos+1]==find_value) //проверяем равна ли средняя позиция искомому элементу
    {
        index=pos+1;
        cout<<index<<endl;
        return 0;
    }
    else if(mas[pos-1]==find_value) //проверяем равна ли средняя позиция искомому элементу (если размер массива не четный)
    {
        index=pos-1;
        cout<<index<<endl;
        return 0;
    }
 
    while(true)
    {
        if(mas[pos]==find_value) //найден ли элемент
        {
            index=pos;
            break;
        }
        else if(mas[pos]<find_value) //если искомый находится во второй половине 
            pos=((size-pos)/2)+pos;  //индекс отнимаем о размера массива делим на 2 и добавляем индекс тоесьт находим треть четверть и т.д.
        else if(find_value<mas[pos]) //если искомый находится в первой половине то делим её на 2
            pos/=2;
 
        if(pow(2.0,count)>size) //если кол-во 2^итераций превышает размера массива то нет такого элемента
        {
            cout<<count<<endl;
            cout<<"The value have not found"<<endl;
            return 1;
        }
        count++;
    }
    cout<<index<<endl;
}


Добавлено через 26 минут
Все нашел ошибки, в эти 10% я не вхожу.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.02.2015, 13:39
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Бинарный поиск (C++):

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

Бинарный поиск - C++
за какое время работает бинарный поиск?

Бинарный поиск - C++
Писал алгоритм бинарного поиска по массиву строк. В результате, почему-то, периодически функция не находит строку, которая есть. int...

Бинарный поиск - C++
Вообщем, написал бинарный поиск, а он не работает для ключа со значением 9, может кто объяснить, как решить эту проблему? А ещё я не совсем...

Бинарный поиск - C++
Найти индекс расположения числа 15 в массиве на 20 элементов и сумму элементов предшествующих ему. Методом бинарного поиска. Вот код в...

Бинарный поиск - C++
Вот вроде бы всё работает только как-то не очень правильно не находит 2 позицию в массиве и пред последнею может ещё что-то не находит , я...

3
DiffEreD
1440 / 777 / 95
Регистрация: 21.06.2011
Сообщений: 1,740
Записей в блоге: 2
02.02.2015, 14:14 #2
Цитата Сообщение от Mikhail1990 Посмотреть сообщение
И дать более оптимальный вариант!
std::binary_search
1
Dimension
Dimension
573 / 442 / 136
Регистрация: 08.04.2014
Сообщений: 1,709
Завершенные тесты: 1
02.02.2015, 17:00 #3
вы серьезно ?неужели так сложно загуглить бинпоиск?и да,ваш бинпоиск не очень.
0
Mikhail1990
22 / 21 / 4
Регистрация: 22.03.2014
Сообщений: 256
02.02.2015, 17:05  [ТС] #4
Dimension, после написания провел много времени в поисках другого варианта, так как понравившегося мне я не нашел (мне мой казался достаточно хорошим) я и создал тему для критики. После я обнаружил что это не поиск, а ерунда, но удалить тему тут нельзя.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.02.2015, 17:05
Привет! Вот еще темы с ответами:

Бинарный поиск - C++
Реализуйте алгоритм бинарного поиска. Входные данные В первой строке входных данных содержатся натуральные числа N и K . Во второй...

Бинарный поиск - C++
Здравствуйте, помогите пожалуйста написать бинарный поиск одного элемента, текст читается из файла. Лабу сдавать в понедельник а я не знаю...

Бинарный поиск - C++
Каким образом выполнить бинарный поиск определнного значения в отсортированном массиве?

Бинарный поиск - C++
Всем привет! У меня вот тут маленькая проблемка! Помогите исправить, а то сама что-то не могу!! (( Когда прога просит ввести ключ...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru