Обнаружение краев Двоичный поиск

Представьте себе веб-сайт, который ежедневно публикует количество ежедневных пассажиров только в графической форме с использованием гистограммы. Я хочу определить число, прочитав гистограмму после сохранения графика в виде изображения (материал изображения здесь не важен). Я хочу читать столбчатую диаграмму, переходя к номеру пикселя (ось количества пассажиров) и задавая вопрос: «Является ли пиксель «включенным» или «выключенным»?» (Вкл. означает, что полоса присутствует, а выкл. означает, что это предположение слишком высокое) Примечание: существует нижняя граница, равная 0, и, технически, бесконечная верхняя граница. Но на самом деле реалистичной верхней границей может быть 10000. Также обратите внимание: «Нет изменений со вчерашнего дня» — это частый вывод.

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

(На мой взгляд, не связанный с CS, это похоже на бинарный поиск с поиском границ, но без предопределенного массива. Могу сказать, что я уже многому научился в поиске.)

Мой алгоритм следует как функция. Любые советы приветствуются.

def EdgeFind(BlackOrWhite,oldtrial,high,low):
# BlackOrWhite is a 0 or 1 depending on if the bar is present or not.  A 1 indicates that you are below or equal to the true number.  A 0 indicates that you are above the true number

# the initial values for oldtrial, high, and low all equal yesterday's value

 factorIncrease = 4#5
 finished = 0

 if BlackOrWhite == 1 and oldtrial==high:
    newtrial = oldtrial+factorIncrease*(high-low)+1
    high = newtrial
    low = oldtrial
 elif BlackOrWhite == 1 and high-oldtrial==1:
    finished = 1
    newtrial = oldtrial
 elif BlackOrWhite == 1:
    newtrial = oldtrial+(high-oldtrial)/2
    low = oldtrial

 if BlackOrWhite == 0 and oldtrial==low:
    newtrial = (oldtrial)/2
    high = oldtrial
    low = newtrial
 elif BlackOrWhite == 0 and oldtrial-low==1:
    finished = 1
    newtrial = oldtrial-1
 elif BlackOrWhite == 0:
    newtrial = oldtrial-(oldtrial-low+1)/2
    high = oldtrial

 if (oldtrial==1) and low!=1:
    finished = 1

 return finished,newtrial,high,low

algorithm binary-search
person Mark    schedule 08.12.2012    source источник
comment
В чем вопрос? Если вы хотите, чтобы ваш код был проверен, разместите его на CodeReview.SE. Если ваш алгоритм не сработает - сообщите об этом. Если это что-то другое, пожалуйста, прямо скажите, что это такое   -  person amit    schedule 09.12.2012
comment
Мой вопрос: как лучше всего найти то, что я называю преимуществом? Любое руководство приветствуется. (Мой код работает нормально, но я не знаю, самый ли это эффективный алгоритм)   -  person Mark    schedule 09.12.2012

Ответы (1)


arrow_upward
1
arrow_downward

Вызов ребра действительно может быть выполнен с помощью модифицированного бинарного поиска.

Это похоже на этот вопрос: Найти элемент в отсортированном массиве бесконечной длины.

Пусть искомый индекс будет idx

Учитывая значение вчерашнего дня, вам нужно найти «край», сделать это можно с экспоненциальным увеличением/уменьшением idx.

Например, если вчера было 1000, вы будете искать в 1000,1001,1002,1004,1008,1016,1032,..., пока не обнаружите, что пиксель изменил переключатель в цвете.

Допустим, вы нашли его на итерации i, это означает, что искомое ребро находится где-то в диапазоне: [1000 + 2^(i-1), 1000 + 2^i]. (конечно, то же самое относится и к вниз, а не к [1000 - 2^(i-1), 1000 - 2^i].

Теперь у вас есть классическая задача бинарного поиска в этом диапазоне.

Сложность остается O(logN), где N — высота изменения со вчерашнего дня.

person amit    schedule 08.12.2012
comment
Спасибо. Это дает мне пищу для размышлений. Очень признателен. - person Mark; 09.12.2012