Блог

Главная - Вопросы по программированию - двоичный поиск с использованием цикла for в javascript

двоичный поиск с использованием цикла for в javascript

#javascript #algorithm #data-structures #binary-search

Вопрос:

Я пытаюсь реализовать двоичный поиск с помощью цикла for в javascript, но это не удается в некоторых тестовых случаях, ниже приведен мой код

 function binarySearch(arr, val){
    let start = 0
    let end = arr.length - 1
    let middle = Math.floor((start   end)/2)

    for(let i = start; i<= end; i  ){
        if(val === arr[middle]) { 
           return middle
        }

        if(val < arr[middle]){
            end = middle - 1
        }

        if(val > arr[middle]){
           start = middle   1
        }

        middle = Math.floor((start   end)/2)
    }
        return -1
  }

    // test case:1 console.log(binarySearch([5, 6, 9, 10, 13, 14, 18, 30, 34, 35, 37, 40, 44, 64, 79, 84, 86, 95, 96, 98, 99], 9))
    
    
   // test case:2 console.log(binarySearch([1,3,4,5,6,7,8,9, 10], 10))

Он проходит 2-й тест, но с треском проваливает 1-й. Кто-нибудь может пролить немного света, пожалуйста?

Комментарии:

1. Похоже, у вас опечатка. val > middle должно быть val > arr[middle] .

2. if(val > middle) ?

3. @Ouroborus, хотя ваше предложение верно, но проблема все равно будет сохраняться. Я понял, почему бы не использовать «для цикла» в этом случае. Это происходит потому, что внутри цикла я присваиваю start новое значение, но проблемы возникают, когда вы понимаете, что значение «i» остается тем же изначально инициализированным начальным значением. То же самое происходит и с i Я имею в виду, что «я» не переназначается ничем, кроме i . Я осознал тот факт, что в этих ситуациях лучше использовать итерацию цикла while.

Ответ №1:

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

Итеративная реализация двоичного поиска (на Java):

 public int binarySearch(int[] array, int target) {
    var left = 0;
    var right = array.length - 1;

    while (left <= right) { 
        var middle = (left   right) / 2;

        if (array[middle] == target)
            return middle;

        if (target < array[middle]) 
            right = middle - 1;
        else
            left = middle   1;
    }

    return -1;
}

Ответ №2:

Я понял, почему бы не использовать «для цикла» в этом случае.

Это связано с тем, что внутри цикла я присваиваю «start» новое значение, но возникают проблемы, когда вы сталкиваетесь с тем фактом, что значение «i» остается тем же ранее инициализированным значением «start».

То же самое происходит с, i

Я имею в виду, что «я» не переназначается ничем, кроме i . Я осознал тот факт, что в этих ситуациях лучше использовать итерацию цикла while вместо цикла for, где вам нужно повторно инициализировать индекс внутри цикла.

Метки: