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

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

Войти
Регистрация
Восстановить пароль
 
Evgen2sat
19 / 19 / 7
Регистрация: 22.11.2011
Сообщений: 101
#1

бинарный поиск по интервалу - C++

24.04.2012, 19:42. Просмотров 810. Ответов 8
Метки нет (Все метки)

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int Search1(data *list, int count,int left,int right) /* list указатель на структуру, count количество элементов, left левая граница поиска, right правая граница поиска*/
{
   int mid; //середина
   int low = 0; int high = count-1;
   while(left <= right) 
   {
     mid = (high+low)/2;
     if(left <= list[mid].key) 
     {
         return mid;
         right = mid-1;
     }
     if(right >= list[mid].key) 
     {
         return mid;
         left = mid+1;
     }
     else return mid; 
   }
   return -1;
}
помогите с бинарным поиском, в общем задается левая и правая граница, и то что между ними должно выводится, т.е. функция должна возвращать индекс левого значения и индекс правого, а потом все что между ними надо вывести. помогите подправить чтобы все работало
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.04.2012, 19:42
Здравствуйте! Я подобрал для вас темы с ответами на вопрос бинарный поиск по интервалу (C++):

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

Бинарный поиск - C++
Написал программу бинарного поиска элемента v. Не могу понять в чем ошибка, не считает количество элементов массива удовлетворяющий...

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

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

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

Бинарный поиск - C++
Прочитал статью на хабре, о том, что только 10 проц программистов смогут реализовать бин поиск. Раньше никогда с ним не имел дело, прочитав...

8
Kuzia domovenok
1892 / 1747 / 119
Регистрация: 25.03.2012
Сообщений: 5,936
Записей в блоге: 1
24.04.2012, 20:00 #2
покажи хоть структуру data
0
Evgen2sat
19 / 19 / 7
Регистрация: 22.11.2011
Сообщений: 101
24.04.2012, 20:30  [ТС] #3
Kuzia domovenok, вот структура
C
1
2
3
4
5
6
struct data
{
    int key;
    float money;
    char name[255];
};
0
Kuzia domovenok
1892 / 1747 / 119
Регистрация: 25.03.2012
Сообщений: 5,936
Записей в блоге: 1
24.04.2012, 21:01 #4
бинарный поиск работает только для упорядоченных(отсортированных) последовательностей. Ты это знаешь?
Что у тебя возвращает функция? Обычно функция поиска возвращает индекс найденного элемента. А у тебя что?

что такое left и right как они связаны с high и low

какой смысл в цикле while(left <= right) если не завершив и одной итерации происходит return???

Добавлено через 10 минут
Я пытаюсь проследить ту цепочку мыслей создателя этого "алгоритма", что привела его к такому.
что по твоему, если, например я буду искать что-то в массиве из 100 элементов,
оно непременно будет находится на месте mid-1 либо mid либо mid+1, где mid=50
Ты так рассуждал? Или от балды где-то что-то слышал вроде: "что-то делим пополам и что-то ещё" и на основе этого сел писать программу???
0
Evgen2sat
19 / 19 / 7
Регистрация: 22.11.2011
Сообщений: 101
24.04.2012, 21:11  [ТС] #5
Kuzia domovenok, нет не от балды, мне надо было реализовать поиск по совпадению и поиск по интервалу (используя двоичный поиск), поиск по совпадению я реализовал, по совпадению не могу, т.е. теоретически понятно как его сделать, а программно не могу реализовать. Вот полный код программы:
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
#include <stdio.h>
#include <conio.h>
#include <locale.h>
#include <malloc.h>
#include <math.h>
 
struct data
{
    int key;
    float money;
    char name[255];
};
 
int Search(data *list, int count, int key) //поиск по совпадению
{
  int low, high, mid;
  low = 0; high = count-1;
  while(low <= high) 
  {
    mid = (low+high)/2;
    if(key < list[mid].key) high = mid-1;
    else if(key > list[mid].key) low = mid+1;
    else return mid; 
  }
  return -1;
}
 
int Search1(data *list, int count,int left,int right)//здесь должен быть поиск по интервалу
{
  
 
}
 
void Sort(data *arr, int size,int find,int low,int high)
{
    data tmp;
    for(int i = 0; i < size - 1; ++i) // i - номер прохода
    {            
        for(int j = 0; j < size - 1; ++j) // внутренний цикл прохода
        {     
            if (arr[j + 1].key < arr[j].key) 
            {
                tmp = arr[j + 1]; 
                arr[j + 1] = arr[j]; 
                arr[j] = tmp;
            }
        }
    }
    int result=Search(arr, size, find);
    if(result!=-1)
    {
    printf("Поиск по совпадению:\n");
    printf("Имя\tВозраст\tЗ/п\n");
    printf("%s\t%d\t%f\n", arr[result].name,arr[result].key,arr[result].money);
    }
    else
    {
        printf("Поиск по совпадению:\n\n");
        printf("Ничего не найдено\n");
    }
    printf("Поиск по интервалу:\n");
    printf("Имя\tВозраст\tЗ/п\n");
    int result1=Search1(arr, size,low,high); /*здесь надо выводить результат поиска по интервалу(не дописано) */
}
 
 void main()
 {
    setlocale(LC_ALL, "RUS");
    int elem;
    int keyStart,keyEnd,find;
    printf("Ведите количество людей: ");
    scanf("%d",&elem);
    struct data *list=(struct data*)malloc(elem*sizeof(data));
    for(int i=0;i<elem;i++)
    {
        printf("Введите %d имя: ",i+1);
        scanf("%s",&list[i].name);
        printf("Введите возраст %d человека: ",i+1);
        scanf("%d",&list[i].key);
        printf("Введите %d з/п: ",i+1);
        scanf("%f",&list[i].money);
    }
    printf("Введите начальный возраст для поиска: ");
    scanf("%d",&keyStart);
    printf("Введите конечный возраст для поиска: ");
    scanf("%d",&keyEnd);
    printf("Введите возраст для поиска: ");
    scanf("%d",&find);
    Sort(list, elem,find,keyStart,keyEnd);
    getch();
    return;
 }
0
Kuzia domovenok
1892 / 1747 / 119
Регистрация: 25.03.2012
Сообщений: 5,936
Записей в блоге: 1
24.04.2012, 21:24 #6
C++
1
2
3
4
5
6
7
8
9
10
int Search1(data *list, int left,int right, int target){
 //ща напишу
 if (target==list[left]) return left;
 if (target==list[right]) return right;
 if (left==right) return -1;
 int mid=(left+right)/2;
 if (list[mid]>=target) return Search1(list, left, mid, target);
 else
 return Search1(list, mid+1, right, target);
}
Добавлено через 11 минут
или итерациями.
C++
1
2
3
4
5
6
7
8
9
10
11
int Search2(data *list, int n, int target){
 int left=0, right=n-1, mid;
 while (left<right){
  if (list[left]==target) return left;
  if (list[right]==target) return right;
  mid=(left+right)/2;
  if (list[mid]<target) left=mid;
  else right=mid;
 }
 return -1;
}
0
Evgen2sat
19 / 19 / 7
Регистрация: 22.11.2011
Сообщений: 101
24.04.2012, 21:25  [ТС] #7
Kuzia domovenok, а что такое target?
и у меня ни первой ни второй написанной вами функцией не ищет элементы в интервале
0
Kuzia domovenok
1892 / 1747 / 119
Регистрация: 25.03.2012
Сообщений: 5,936
Записей в блоге: 1
24.04.2012, 21:52 #8
А какой по-твоему элемент ты ищешь?
Ты вообще думал, для чего твоя программа предназначена? Для поиска числа target в массиве list
ААА дошло, ты действительно интервал ищешь, а я всё это время про другое думал
0
Evgen2sat
19 / 19 / 7
Регистрация: 22.11.2011
Сообщений: 101
24.04.2012, 21:58  [ТС] #9
Kuzia domovenok, так поможешь написать функцию поиска по интервалу?
0
24.04.2012, 21:58
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.04.2012, 21:58
Привет! Вот еще темы с ответами:

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

Бинарный поиск - C++
Добрый день , возникла проблема с бинарным поиском . Я его просто нашел в интернете и вставил в программу не много отредактировав . Вобщем...

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

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


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

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

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