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

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

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

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

06.07.2009, 19:36. Просмотров 2787. Ответов 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++
Произвожу поиск элемента в массиве двумя способами: линейным(последовательным) поиском и бинарным(двоичным). Первый работает на ура. Второй...

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

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

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

Бинарный поиск - C++
помоги мне плиз ответить на вопросы Бинарный поиск #include &lt;iostream&gt; using namespace std; int BinSearch(int *M, int n,...

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

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
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
17634 / 5858 / 378
Регистрация: 30.03.2009
Сообщений: 16,160
Записей в блоге: 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
Эксперт С++
8286 / 3505 / 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
2359 / 1054 / 44
Регистрация: 03.05.2009
Сообщений: 2,656
06.07.2009, 21:18 #11
Duran,
Уже пол дня творю,3 листа исписал и ничего не получается
потому что надо не просто наугад тыркаться в коде, а понимать, "чё тама происходит, в натуре".
Скачай Кнута "Искусство программирования", ты потратишь 1 час и пол-листа, и всё получится.
Duran
0 / 0 / 0
Регистрация: 21.06.2009
Сообщений: 13
06.07.2009, 21:49  [ТС] #12
Цитата Сообщение от Rififi Посмотреть сообщение
Duran,
Скачай Кнута "Искусство программирования", ты потратишь 1 час и пол-листа, и всё получится.
благодарю.Надеюсь это последняя моя глупая тема.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.07.2009, 21:49
Привет! Вот еще темы с ответами:

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

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

Бинарный поиск - C++
#include &lt;iostream&gt; #include &lt;fstream&gt; #include &lt;algorithm&gt; #include &lt;string&gt; #include &lt;vector&gt; using namespace std; ...

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


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
06.07.2009, 21:49
Ответ Создать тему
Опции темы

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