Бинарный поиск выходит рано? - PullRequest
Новая
       15

Бинарный поиск выходит рано?

0 голосов
/ 24 июня 2019

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

function bSearch(arr, num) {
  let start = 0
  let end = arr1.length - 1
  while (start <= end) {
    let middle = Math.round(start + end / 2)
    if (arr[middle] === num) {
      return arr[middle]
    } else if (arr[middle] < num) {
      start = middle
    } else {
      end = middle
    }
  }
  return false
}

function dup(arr1, arr2) {
  let output = []
  let shorterArray = arr1.length > arr2.length ? arr2 : arr1
  for (let i = 0; i < shorterArray.length; i++) {
    if (bSearch(arr1, shorterArray[i])) {
      output.push(shorterArray[i])
    }
  }
  return output
}

let arr1 = [1, 2, 3, 5, 6, 7], arr2 = [3, 6, 7, 8, 20]
dup(arr1, arr2)

// should return [3, 5, 7]
// currently only returns [3]

1 Ответ

1 голос
/ 24 июня 2019

Ряд небольших вопросов здесь.

  1. bSearch(arr1, shorterArray[i]) - в случае короткого arr1 вы ищете только его.

  2. В вашем бинарном поиске вы используете длину arr1, а не arr для начального end переменной переменной.

  3. let middle = Math.round(start + end / 2) - .round() округляет по-разному, используйте .floor().

  4. Math.round((start + end) / 2 - start и end сложение должно быть в скобках

  5. Двоичная логика должна увеличивать или уменьшать среднее значение, иначе вы окажетесь в бесконечном цикле, т.е. (6 + 6)/2 === 6

Таким образом: 

if (arr[middle] === num) {
    return arr[middle]
} else if (arr[middle] < num) {
    start = middle + 1
} else {
    end = middle - 1
}

JsBin: https://jsbin.com/ciyusodisi/edit?js,console

...