Objective-C: наиболее эффективный способ отобразить число в соответствии с NSRange в NSDictionary

Question

У меня есть много объектов с соответствующими диапазонами:

Object1 => 0 - 23
Object2 => 24 - 84
Object3 => 85 - 103
...

Эти диапазоны меняются, теперь я ищу наиболее эффективный способ в Objective-C сказать: «Хорошо, я имеюполучил число 56; какой объект имеет соответствующий диапазон? Ах, да: это Object2 ".

Есть идеи?Бинарный поиск?Что-то еще?

Большое спасибо!

Answer 1

Это похоже на поиск позиции указанного значения в отсортированном списке различных точек вашего сегмента, в вашем случае вы можете взять, например: [-0.5,23.5,84.5,103.5] это список средняя точка между началом и концом каждого сегмента.

если указанная вами позиция равна 1 => объект 1

если 2 => object2

если это 3 => объект 3

За 56 вы получите 2 => объект 2

надеюсь, это поможет

---

Редактировать:

Для массива A размера N псевдокод для этого модифицированного двоичного поиска будет.

  min := 0; //my array start at index 0
  max := N-1; 
  repeat
    mid := (min+max) div 2;
    if x > A[mid] then
      min := mid + 1;
    else
      max := mid - 1;
  until (A[mid+1] > x >A[mid]) or (min > max);
  return mid+1

Я изменял условие до (ср. статья в Википедии о бинарном поиске ), чтобы соответствовать ограничению проблемы. Я изменяю середину, пока х не окажется между 2 элементами, и я возвращаю середину + 1