Путаница с начальным и конечным индексами в бинарном поиске - PullRequest
Новая
       26

Путаница с начальным и конечным индексами в бинарном поиске

0 голосов
/ 27 мая 2019

Ниже приводится бинарный поиск из этой записи .s означает начальный индекс, e означает конечный индекс.Я думаю, что понимаю их. 

function bs(arr, tar) {
  let s = 0;
  let e = arr.length - 1;

  while(s <= e) {
    let m = Math.floor((s + e) / 2);

    if(tar === arr[m]) {
      return m;
    }

    if(tar > arr[m]) {
      s = m + 1; // follow index
    }

    if(tar < arr[m]) {
      e = m - 1; // follow index
    }
  }

  return -1;
}

let arr = [1, 2, 3, 4, 5, 6, 7];
let tar = 5;
let out = bs(arr, tar);
console.log(out);

Иногда я также вижу эту версию: 

function bs(arr, tar) {
  let s = 0;
  let e = arr.length; // full len

  while(s < e) {
    let m = Math.floor((s + e) / 2);

    if(tar === arr[m]) {
      return m;
    }

    if(tar > arr[m]) {
      s = m + 1; // because s=0;
    }

    // end, exact index
    if(tar < arr[m]) {
      e = m; // not m-1, because arr.length???
    }
  }

  return -1;
}

let arr = [1, 2, 3, 4, 5, 6, 7];
let tar = 5;
let out = bs(arr, tar);
console.log(out);

Думаю, через некоторое время я понимаю, что означают индексы.

1 Ответ

0 голосов
/ 27 мая 2019

Для бинарного поиска нужен упорядоченный список, например, список чисел. Идея состоит в том, чтобы искать элемент в правой половине, и это возможно, потому что этот алгоритм сходится к одному. Допустим, у вас есть список из 10 (1, 10, 54, 70, 100, 110, 120, 130, 150, 200) чисел, и вы ищете 120. Вы делите список на две половины и ищите средний элемент (100) 120 больше 100? Да, так что элемент находится во второй половине, теперь начальная точка - это средняя позиция, а конечная позиция - это конец списка, вы продолжаете, пока у вас не появится тот элемент, который вы ищете. Надеюсь, что это было полезно

...