1

Решил для тренировки написать функцию бинарного поиска целых чисел в массиве. Есть два массива и функция:

let arr1 = [1, 2, 3, 4, 5, 6, 7, 8, 9];
let arr2 = [9, 8, 7, 6, 5, 4, 3, 2, 1];

let binarySerch = (arr, num) => {

    let currentIndex = arr.length / 2;

    if (arr[0] == num) return 0;

    while (arr[currentIndex] != num) {
        if (arr[currentIndex] < num) currentIndex /= 2;
        else currentIndex *= 2;
    }
    if (currentIndex == 1 && arr[0] != num) return -1;
    return currentIndex;
}

Эта функция по идее должна работать для массива сортированного по убыванию. Можно ли как-то адаптировать ее под массив сортированный по возрастанию тоже, но не дублировать код? Например, написать что-то типа:

if(arr[arr.length -1] < arr[arr.length -2]) // сортирован по убыванию и надо двигаться в одном направлении, иначе - в противоположном  
2
  • 1
    Адаптировать можно. Но сперва нужно исправить ошибку. Сейчас это не двоичный поиск. 9 июн 2021 в 6:08
  • если в массиве числа могут повторяться - то, для проверки сортированности необходимо будет пройтись по всему массиву. Сравнение двух элементов не хватит.
    – Grundy
    9 июн 2021 в 6:27

2 ответа 2

1

Если поработать напильником, то можно сделать так.

let arr1 = [1, 2, 3, 4, 5, 6, 7, 8, 9];
let arr2 = [9, 8, 7, 6, 5, 4, 3, 2, 1];


let binarySearch = function(arr, num, order="asc"){
   
    let start=0
    let end=arr.length-1;
    
    while (start<=end){
    
        let mid=((start + end)/2) | 0;
        if (arr[mid]=== num) return mid;
        else if ((arr[mid] < num) == (order == "asc")) 
             start = mid + 1;
        else
             end = mid - 1;
    }
    
    return -1;
}

console.log(binarySearch(arr1, 2));
console.log(binarySearch(arr2, 2, "desc"));

0

Для массива отсортированного по возрастанию достаточно проверять противоположное условие, когда решаете в какой из половин нужно продолжать поиск, т.е. проверять условие arr[currentIndex] > num.

Чтоб совместить это в одной функции, можно передать какой именно результат сравнения мы ожидаем:

let binarySerch = (arr, num, sort_descending = true) => {

    let currentIndex = arr.length / 2;

    if (arr[0] == num) return 0;

    while (arr[currentIndex] != num) {
        if ((arr[currentIndex] < num) == sort_descending) currentIndex /= 2;
        else currentIndex *= 2;
    }
    if (currentIndex == 1 && arr[0] != num) return -1;
    return currentIndex;
}

Тогда для сортировки по убыванию вызов будет как и раньше:

binarySearch(arr, num)

или

binarySearch(arr, num, true)

Для отсортированного по возрастанию вызываем так:

binarySearch(arr, num, false)

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.