J
J
justifycontent2021-05-01 09:54:55
JavaScript
justifycontent, 2021-05-01 09:54:55

Is binary search correct?

const binarySearch = (list, n) => {
    let start = 0,
        end = list.length - 1,
        mid;
    
    while(start <= end) {
      mid = Math.floor((start + end) / 2);
      if (n < list[mid]) {
        end = mid - 1;
      } else if (n > list[mid]) {
        start = mid + 1;
      } else {
        return `Искомое ${n} найдено на ${mid} индексе(${list[mid]})`;
      }
    }

    return `Искомое ${n} не найдено!`;
  }

Answer the question

In order to leave comments, you need to log in

2 answer(s)
U
user_of_toster, 2021-05-01
@justifycontent

mid = Math.floor((start + end) / 2);
You can not calculate in advance and write only inside the while loop.
n !== list[mid]
If the desired value is in the middle, then your binary search will break. This condition must be removed, because there is

else {
        return `Искомое ${n} найдено на ${mid} индексе(${list[mid]})`;
      }

mid !== start && mid !== end
Here, due to floorbugs, there may be bugs, and the search may end earlier. Better to replace withstart <= end

J
jcmvbkbc, 2021-05-01
@jcmvbkbc

Is binary search correct?

No, it's not true. Try them to find 1 in the array {0, 1}.

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question