Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.85/13: Рейтинг темы: голосов - 13, средняя оценка - 4.85
19 / 19 / 13
Регистрация: 22.11.2011
Сообщений: 101
1

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

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

Author24 — интернет-сервис помощи студентам
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
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
24.04.2012, 19:42
Ответы с готовыми решениями:

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

Бинарный поиск
помоги мне плиз ответить на вопросы Бинарный поиск #include &lt;iostream&gt; using namespace std;...

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

Бинарный поиск
Здравствуйте, не могу понять как составить алгоритм: нужно найти сумму элементов в массиве, которые...

8
4064 / 3318 / 924
Регистрация: 25.03.2012
Сообщений: 12,493
Записей в блоге: 1
24.04.2012, 20:00 2
покажи хоть структуру data
0
19 / 19 / 13
Регистрация: 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
4064 / 3318 / 924
Регистрация: 25.03.2012
Сообщений: 12,493
Записей в блоге: 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
19 / 19 / 13
Регистрация: 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
4064 / 3318 / 924
Регистрация: 25.03.2012
Сообщений: 12,493
Записей в блоге: 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
19 / 19 / 13
Регистрация: 22.11.2011
Сообщений: 101
24.04.2012, 21:25  [ТС] 7
Kuzia domovenok, а что такое target?
и у меня ни первой ни второй написанной вами функцией не ищет элементы в интервале
0
4064 / 3318 / 924
Регистрация: 25.03.2012
Сообщений: 12,493
Записей в блоге: 1
24.04.2012, 21:52 8
А какой по-твоему элемент ты ищешь?
Ты вообще думал, для чего твоя программа предназначена? Для поиска числа target в массиве list
ААА дошло, ты действительно интервал ищешь, а я всё это время про другое думал
0
19 / 19 / 13
Регистрация: 22.11.2011
Сообщений: 101
24.04.2012, 21:58  [ТС] 9
Kuzia domovenok, так поможешь написать функцию поиска по интервалу?
0
24.04.2012, 21:58
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
24.04.2012, 21:58
Помогаю со студенческими работами здесь

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

Бинарный поиск
Реализация на С++: int Search_Binary (int arr, int left, int right, int key) { int midd = 0; ...

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

Бинарный поиск
Никак не могу понять почему у меня не проходит тесты данный код. Задача выглядит так: Входные...


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

Или воспользуйтесь поиском по форуму:
9
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru