Форум программистов, компьютерный форум CyberForum.ru

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 22, средняя оценка - 4.64
Duran
0 / 0 / 0
Регистрация: 21.06.2009
Сообщений: 13
#1

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

06.07.2009, 19:36. Просмотров 2778. Ответов 11
Метки нет (Все метки)

Задали реализовать бинарный поиск в упорядоченном массиве.Уже пол дня творю,3 листа исписал и ничего не получается.

Вот пример поиска который нам показали
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
//Метод Выбора
    for(i=0;i<n-1;i++)
    {
        min=i;
        for(j=i+1;j<n;j++)
        {
            if(a[j]<a[min])min=j;
        }
            if(min==i)continue;
            temp=a[i];
            a[i]=a[min];
            a[min]=temp;
    }
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
//Метод Вставки
    for(i=1;i<n;i++)
    {
        temp=a[i];
        j=i-1;
        while(j>=0 && temp<a[j])
        {
            a[j+1]=a[j];
            j--;
        }
        j++;
        a[j]=temp;
    }
Помогите пожалуйста с поиском.
Только без "binarySearch" и "*"-(Средний элемент в каждом подмассиве),нам это еще не обьяснили.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.07.2009, 19:36     бинарный поиск
Посмотрите здесь:

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

Бинарный поиск - C++
Вот значит код, бинарный поиск элементов динамического целочисленного массива. #include &lt;iostream&gt; #include &lt;vector&gt; #include...

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

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

Бинарный поиск - C++
Что переделать в программе, чтобы она находила первый элемент больше или равный заданному? #include &quot;stdafx.h&quot; #include &lt;iostream&gt; ...

Бинарный поиск c++ - C++
1) последовательного поиска максимального элемента в одномерном динамическом массиве; 2) бинарного поиска количества нулевых элементов...

Бинарный поиск - C++
Реализовать алгоритм бинарного поиска количества нулевых элементов двумерного динамического массива. Это вообще возможно? Пробовал...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
pigah
12 / 12 / 2
Регистрация: 05.07.2009
Сообщений: 147
Записей в блоге: 1
06.07.2009, 20:00     бинарный поиск #2
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
l = леваяГраница - 1
r = праваяГраница + 1
while (r - l > 1) {
  середина = (l+r) / 2
  if (массив[середина] < значение)
     l = середина
  else
     r = середина
 } 
 if (массив[r] в‰* значение)
   return -1 // элемент не найден
 else
   return r
Duran
0 / 0 / 0
Регистрация: 21.06.2009
Сообщений: 13
06.07.2009, 20:11  [ТС]     бинарный поиск #3
"return" нам тоже не обьясняли.Я так смотрю половину функций которые я должен знать,на данный момент,мне просто не преподают.
pigah
12 / 12 / 2
Регистрация: 05.07.2009
Сообщений: 147
Записей в блоге: 1
06.07.2009, 20:24     бинарный поиск #4
Цитата Сообщение от Duran Посмотреть сообщение
"return" нам тоже не обьясняли.Я так смотрю половину функций которые я должен знать,на данный момент,мне просто не преподают.
return n; - завершение работы и возврат n

Добавлено через 3 минуты 18 секунд
Цитата Сообщение от Duran Посмотреть сообщение
"return" нам тоже не обьясняли.Я так смотрю половину функций которые я должен знать,на данный момент,мне просто не преподают.
посмотри здесь http://www.cyberguru.ru/programming/...ay-page59.html
Duran
0 / 0 / 0
Регистрация: 21.06.2009
Сообщений: 13
06.07.2009, 20:32  [ТС]     бинарный поиск #5
Слушай, сжалься надомной выложи рабочий код,без return, а то у меня сейчас мозг взорвется.
Evg
Эксперт CАвтор FAQ
17464 / 5702 / 361
Регистрация: 30.03.2009
Сообщений: 15,656
Записей в блоге: 26
06.07.2009, 20:35     бинарный поиск #6
Цитата Сообщение от Duran Посмотреть сообщение
Слушай, сжалься надомной выложи рабочий код,без return, а то у меня сейчас мозг взорвется.
А ты не мог просто честно сказать "сделайте мне то-то и то-то", а не начинать тут заливать про то, как ты полдня корячился и в подтверждение своим словам выложить чужой код
Duran
0 / 0 / 0
Регистрация: 21.06.2009
Сообщений: 13
06.07.2009, 20:41  [ТС]     бинарный поиск #7
Цитата Сообщение от Evg Посмотреть сообщение
А ты не мог просто честно сказать "сделайте мне то-то и то-то", а не начинать тут заливать про то, как ты полдня корячился и в подтверждение своим словам выложить чужой код
выложенные коды мне на занятиях обьяснили,я действительно пол дня пытаюсь написать код с известными мне ф-циями и сейчас я просто зае**ся настолько,что прошу уже готовый код.До этого момента я думал что смогу своими силами все сделать.
M128K145
Эксперт С++
8283 / 3502 / 143
Регистрация: 03.07.2009
Сообщений: 10,706
06.07.2009, 20:51     бинарный поиск #8
Вот рабочий код.
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
#include "stdafx.h"
#include <iostream>
 
void main()
{
    int n, src;
    std::cout<<"Size:\t";
    std::cin>>n;
    std::cout<<"Search:\t";
    std::cin>>src;
 
    int *mas = new int[n];//динамический массив
    for(int i = 0; i < n; ++i)//заполнение
        mas[i] = i;
 
    int half = 0;
    int first = 0;
    int middle = 0;
    while (n > 0)
    {
        half = n / 2;
        middle = first + half;
        if (src < mas[middle])
            n = half;
        else
        {
            first = middle + 1;
            n = n - half - 1;
        }
    }
    std::cout<<"\nRezult index:\t"<<first;
    std::cin.get();
    std::cin.get();
}
Если элемент не найден, то возвращается один из крайних индексов, т.е. если заданное число меньше минимального то возвращается 0, если больше максимального то возвращается твой n
Duran
0 / 0 / 0
Регистрация: 21.06.2009
Сообщений: 13
06.07.2009, 21:02  [ТС]     бинарный поиск #9
M128K145, я даже и близко к решению не был.Блин ну как же все просто.
pigah
12 / 12 / 2
Регистрация: 05.07.2009
Сообщений: 147
Записей в блоге: 1
06.07.2009, 21:10     бинарный поиск #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
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
#include "stdafx.h"
#include <iostream>
#include <windows.h>
#include <cmath>
#include <iomanip>
#include <limits.h>
 
const int CP=1251;
 
using namespace std;
 
void main(){
    SetConsoleOutputCP(CP);
    SetConsoleCP(CP);
    srand(GetTickCount());
    const int N=1000;
    int a[N];
    const int A=-800,B=800;
    int i,imin,min,j,t;
    cout<<"\nСортировка массива по возрастанию\n\n\n";
    for(i=0;i<N;i++)
        a[i]=A+rand()%(B-A+1);//создание массива
 
    cout<<"\n\n";
    
    for(i=0; i<N; i++){//Внешний цикл
        imin=i;
        min=a[i];
        for(j=i; j<N; j++){
            if(a[j] < min){
                min=a[j];
                imin=j;
            }//if
        }//for j
        
        //Меняем местами i-й и imin элемент a[i]----a[imin]
        t=a[i];
        a[i]= a[imin];
        a[imin]=t;
    }//for
 
    cout<<"Отсортированый массив по возрастанию\n";
    for(i=0; i<N; i++){
        cout<<setw(5)<<a[i];
        if((i+1)%8==0)cout<<"\n";
    }
    cout<<"\n\n";
 
 
    //---------------------------------------------------------------
    
    int key,middle,right,left;
    bool find;
 
    cout<<"Введите число_";
    cin>>key;
 
    right = N-1;
    left = 0;
    find = false;
    for(;;){
 
        middle=(left + right)/2;
        if(a[middle] == key){
            find=true;
            break;
        }//if
        if (a[middle]<key){
            left=middle;
        }//if
 
        if (a[middle]>key){
            right=middle;
        }//if
        if (abs(left-right)<=1){
            break;
        }//if
    }
    if(find)
        cout<<"Нашли "<<a[middle]<<"\n";
    else{
        cout<<"нет "<<key<<"\n";
    }
}//for
Rififi
2338 / 1053 / 44
Регистрация: 03.05.2009
Сообщений: 2,656
06.07.2009, 21:18     бинарный поиск #11
Duran,
Уже пол дня творю,3 листа исписал и ничего не получается
потому что надо не просто наугад тыркаться в коде, а понимать, "чё тама происходит, в натуре".
Скачай Кнута "Искусство программирования", ты потратишь 1 час и пол-листа, и всё получится.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.07.2009, 21:49     бинарный поиск
Еще ссылки по теме:

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

Бинарный поиск рекурсией - C++
Не могу разобраться, какое условие дописать в функцию для возврата -1, если искомый элемент не найден? int BinSearch(int mas,int Start,...

Двоичный(бинарный) поиск - C++
Столкнулся с такой проблемой. использую бинарный поиск в упорядоченном массиве чисел для поиска количества повторений нужного мне числа К...

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

Бинарный поиск. Задачи - C++
Здравствуйте! Алгоритм бинарного поиска я в принципе знаю и могу решить задачи типа &quot;Найти индекс элемента в массиве&quot;. Но на бинарный...


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

Или воспользуйтесь поиском по форуму:
Duran
0 / 0 / 0
Регистрация: 21.06.2009
Сообщений: 13
06.07.2009, 21:49  [ТС]     бинарный поиск #12
Цитата Сообщение от Rififi Посмотреть сообщение
Duran,
Скачай Кнута "Искусство программирования", ты потратишь 1 час и пол-листа, и всё получится.
благодарю.Надеюсь это последняя моя глупая тема.
Yandex
Объявления
06.07.2009, 21:49     бинарный поиск
Ответ Создать тему
Опции темы

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