Оптимизировать по времени проверку принадлежности числа к числовым диапазонам

Question

Имеется число в диапазоне 0...505 Нужно определить, в какой диапазон оно попадает

диапазоны 5...69 70...139 140...209 210...279 280...349 350...419

При попадании в диапазон вывести число 1, 2, 3, и тд. Язык С (классический), железо 8 битное, операции деления и умножения использовать крайне не желательно.

Первый опробованный вариант решения - деление числа на 70 нацело. Второй вариант - лестница из IF. Оба варианта не проходят по времени.

Answer 1

Что на счёт варианта с шестью if?

if число больше 5 и меньше 69 {вывести 1}
else if число больше 70 и меньше 139 {вывести 2}

и т.д.

Ну или switch case использовать.

Answer 2

Похоже на поиск в сортированном массиве. Разделить массив пополам. Определить в какой половине находиться число потом нужную половину разделить ещё раз пополам и перебрать только четверть массива. Потом уже определить в каком это диапазоне. Диапазоны можно предварительно именовать. Для любого числа это будет одинаковая скорость. Итого 4-е операции, меньше чем количество диапазонов. При желании можно добавить ещё один блок деления массива чтобы перебирать не 1/4, а 1/8 массива. Есть готовый код только без диапазонов.

/*
Поиск в сортированном массиве. Для увеличения эффективности
алгоритма делим массив пополам, ещё раз пополам и перебираем
только нужную четверть массива.
*/
#include <stdio.h>
#include <windows.h>
#include <locale.h>
int main(void)
{
    setlocale(LC_ALL, "RU");
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
char m,y1;
char a[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
int i,y,z,m1,iL,iR;
float q;
    printf("Ищем в массиве: '%s' \n",a);
    //printf("Количество символов в строке - %d\n",strlen(a));
    printf("Выбор символа:\n");
//  Получаем искомый символ и определяем его код.
    scanf(" %c",&m);
y=(int)m;
    printf("Искомый символ - '%c' \nКод символа - '%d'\n",m,y);
//  Находим количество символов в массиве
z=strlen(a);
//  Делим массив пополам приведя к float для нечётного числа
q=(float)z/2;
    //printf("%.1f\n",q);
//  Приводим обратно к int и получаем индекс символа в середине массива.
i=(int)q;
    //printf("Адрес середины массива - а[%d]\n",i);
//  Присваиваем переменной int m1 код символа середины массива
m1=a[i];
    //printf("Середина массива - %d - %c\n", m1, m1);
//  Сравниваем код символа середины массива и код искомого символа
if (m1 >= y)
{
//  Делим пополам левую сторону массива
    iL=i;
    iL+=1;
    iL/=2;
    m1=a[iL];
    if (m1 >= y)
    {
        iL+=1;
//  Перебираем 1/4 массива
        for (iL; iL>=0; iL--)
        {
        m1 = a[iL];
//  Сравниваем код символа, а не индекс
        if (m1 == y)
        printf("Адрес символа в 1/4 массивa - a[%d]\n",iL);
        }
    }
//  Это тот же цикл поиска только в 2/4 массива.
else if (m1 < y)
{
    iL-=1;
//  Перебираем 2/4 массива
    for (iL; iL<=z; iL++)
    {
        m1 = a[iL];
        if (m1 == y)
        printf("Адрес символа в 2/4 массива - a[%d]\n",iL);
    }
}
}
//  Это тот же цикл поиска только в правой половине массива
else if (m1 < y)
{
    iR=i;
    iR-=1;
    iL=i/2;
    iR=i+iL;
    m1=a[iR];
    if (m1 >= y)
    {
        iR+=1;
        for (iR; iR>=i; iR--)
        {
            m1 = a[iR];
//  Сравниваем код символа, а не индекс.
            if (m1 == y)
            printf("Адрес символа в 3/4 массива - a[%d]\n",iR);
        }
    }
//  Это тот же цикл поиска только в правой части  правой половины 
//массива.(4/4)
else if (m1 < y)
{
    iR-=1;
    for (iR; iR<=z; iR++)
    {
        m1 = a[iR];
        if (m1 == y)
        printf("Адрес символа в 4/4 массива - a[%d]\n",iR);
    }
}
}
return 0;
}
// 78 строк (без комментариев)

БЛОГ НА HUSL

Оптимизировать по времени проверку принадлежности числа к числовым диапазонам

Ответы (2 шт):