1 / 1 / 0
Регистрация: 21.06.2016
Сообщений: 11
1

Поиск элемента, меньшего заданного, в упорядоченном массиве

30.06.2016, 11:52. Показов 2399. Ответов 4
Метки нет (Все метки)

Добрый день. Мне необходимо найти в массиве первый элемент, который меньше заданного, и, очень желательно, за логарифм. Массив упорядочен по убыванию. Решил приспособить для этой задачи бинарный поиск. Пробовал несколько вариантов, но у меня в каждом случае поиск выполняется либо в одной, либо в другой половине массива. Подскажите пожалуйста, как можно реализовать это. Ниже выкладываю примерный код, который у меня получился

C++ (Qt)
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
#include <iostream>
#define ARRSIZE 10
 
using namespace std;
 
int search(int* a, int size, int key) {
 
    int left = 0;
    int right = size-1;
    int lastPos = -1;
    if(a[left] < key) { return 0; }
    if(a[right] > key) { return -1; }
 
    while(left < right) {
        int mid = left + (right-left)/2;
        if(a[mid]==key) { return mid; }
        else if(a[mid] < key) {
            right = mid - 1;
            lastPos = mid;
        } else {
            left = mid;
            right = lastPos;
        }
    }
 
    return lastPos;
}
 
int main(void) {
    int arr[ARRSIZE] = {90, 80, 70, 60, 50, 40, 30, 20, 10, 0};
 
    int pos = search(arr, ARRSIZE, 85);
    if(pos != -1) 
        cout << arr[pos];
    else 
        cout << "Not found";
 
    return 0;
}
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
30.06.2016, 11:52
Ответы с готовыми решениями:

Поиск заданного элемента в упорядоченном по возрастанию массиве целых чисел
Осуществить поиск заданного элемента в упорядоченном по возрастанию (по убыванию) массиве целых...

Рекурсивный поиск заданного элемента в массиве
X - массив, состоящий из 100 числовых элементов. Написать программу, которая выдает номер первого...

Реализовать бинарный поиск заданного элемента в массиве
Доброго времени суток, форумчане! Реализую алгоритмы поиска: линейный и бинарный. Нужно, чтоб они...

Реализовать бинарный поиск заданного элемента в массиве
Помогите, напишите бинарный поиск элемента в массиве (особенно чтобы он работал, когда все элементы...

4
161 / 153 / 92
Регистрация: 18.11.2015
Сообщений: 677
30.06.2016, 12:10 2
Уалил
1
1 / 1 / 0
Регистрация: 21.06.2016
Сообщений: 11
30.06.2016, 12:16  [ТС] 3
Благодарю за ответ, но мне нужно не просто бинарным поиском найти элемент, а найти ближайший к нему по значению, который меньше или равен данному
0
161 / 153 / 92
Регистрация: 18.11.2015
Сообщений: 677
30.06.2016, 13:10 4
Лучший ответ Сообщение было отмечено RoneDePuh как решение

Решение

RoneDePuh, да, понимаю, я невнимательно прочитал задание, сори

Добавлено через 49 минут
RoneDePuh, может, так. Я, правда, не силен в этих штуках.

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
#include <iostream>
#define ARRSIZE 10
 
using namespace std;
 
size_t search(int* a, int size, int key) {
 
    size_t high = 0;
    size_t low = size - 1;
    size_t mid = (low + high) / 2;
    
    if (a[high] < key) return high;
    if (a[high] == key) return high + 1;
    if (a[low] >= key) return -1;
 
    while (mid != high && mid != low)
    {
        if (low == high) return low == 0 ? low + 1 : low;
 
        mid = (low + high) / 2;
 
        if (a[mid] >= key)
            high = mid + 1;
        else 
            low = mid - 1;
    }
 
    return mid;
}
 
int main(void) {
    int arr[ARRSIZE] = { 90, 80, 70, 60, 50, 40, 30, 20, 10, 0 };
 
    size_t pos = search(arr, ARRSIZE, 12);
    if (pos != -1)
        cout << arr[pos] << std::endl;
    else
        cout << "Not found" << std::endl;
 
    std::cin.get();
    return 0;
}
Добавлено через 2 минуты
RoneDePuh, этот код очень привязан к массиву, который упорядочен по убыванию.
1
1 / 1 / 0
Регистрация: 21.06.2016
Сообщений: 11
30.06.2016, 13:57  [ТС] 5
Спасибо огромное. Ошибка небольшая была. При входном значении 25, возвращался индекс 30, но я исправил это.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
30.06.2016, 13:57
Помогаю со студенческими работами здесь

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

Двоичный поиск в упорядоченном массиве
Дан упорядоченный по неубыванию целочисленный массив и набор чисел ki. Требуется для каждого числа...

Функция, выполняющая поиск заданного элемента в одномерном массиве типа double
Написать функцию, выполняющую поиск заданного элемента в одномерном массиве типа double. Параметры...

В отсортированном одномерном массиве выполнить поиск заданного элемента последовательным методом
Знаю,что тут есть похожая очень тема, но не могу справиться который день...так что прошу...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru