Ответ 1

Вы явно не возвращаете рекурсивные внутренние вызовы (т.е. return binarySearch()), поэтому стек вызовов разворачивается без возвращаемого значения. Обновите свой код так:

// ...
if (arr[mid] === i) {
    console.log('match', arr[mid], i);
    return arr[mid];
} else if (arr[mid] < i && arr.length > 1) {
    console.log('mid lower', arr[mid], i);
    return binarySearch(arr.splice(mid, Number.MAX_VALUE), i);
} else if (arr[mid] > i && arr.length > 1) {
    console.log('mid higher', arr[mid], i);
    return binarySearch(arr.splice(0, mid), i);
} else {
// ...

См. рабочая скрипка

Ответ 2

Полезно написать функцию поиска таким образом, чтобы она возвращала отрицательное значение, указывающее точку вставки для нового элемента, если элемент не найден. Кроме того, использование рекурсии в двоичном поиске является чрезмерным и ненужным. И, наконец, хорошая практика сделать общий алгоритм поиска, предоставив функцию компаратора в качестве параметра. Ниже приведена реализация.

function binarySearch(ar, el, compare_fn) {
    var m = 0;
    var n = ar.length - 1;
    while (m <= n) {
        var k = (n + m) >> 1;
        var cmp = compare_fn(el, ar[k]);
        if (cmp > 0) {
            m = k + 1;
        } else if(cmp < 0) {
            n = k - 1;
        } else {
            return k;
        }
    }
    return -m - 1;
}

Этот код с комментариями и unit test здесь.

Ответ 3

Есть много действенных решений этого вопроса, но все они возвращаются рано, как только нашли совпадение. Хотя это может оказать небольшое положительное влияние на производительность, это незначительно из-за логарифмической природы бинарного поиска и может фактически снизить производительность, если функция сравнения является дорогостоящей для вычисления.

Более того, он предотвращает очень полезное применение алгоритма бинарного поиска: поиск диапазона совпадающих элементов, также известный как поиск нижней или верхней границы.

Следующая реализация возвращает индекс 0 ≤ i ≤ array.length, так что данный предикат имеет значение false для array[i - 1] и true для array[i]. Если предикат false везде, array.length возвращается.

/**
 * Return 0 <= i <= array.length such that !pred(array[i - 1]) && pred(array[i]).
 */
function binarySearch(array, pred) {
    let lo = -1, hi = array.length;
    while (1 + lo < hi) {
        const mi = lo + ((hi - lo) >> 1);
        if (pred(array[mi])) {
            hi = mi;
        } else {
            lo = mi;
        }
    }
    return hi;
}

Ответ 4

Вот функция двоичного поиска, вы можете проверить

   function bsearch (Arr,value){
        var low  = 0 , high = Arr.length -1 ,mid ;      
        while (low <= high){
            mid = Math.floor((low+high)/2);     
            if(Arr[mid]==value) return mid ; 
            else if (Arr[mid]<value) low = mid+1;
            else high = mid-1;          
        }
        return -1 ;
    }

Ответ 5

Это мое решение!

// perform a binarysearch to find the position in the array
function binarySearch(searchElement, searchArray) {
    'use strict';

    var stop = searchArray.length;
    var last, p = 0,
        delta = 0;

    do {
        last = p;

        if (searchArray[p] > searchElement) {
            stop = p + 1;
            p -= delta;
        } else if (searchArray[p] === searchElement) {
            // FOUND A MATCH!
            return p;
        }

        delta = Math.floor((stop - p) / 2);
        p += delta; //if delta = 0, p is not modified and loop exits

    }while (last !== p);

    return -1; //nothing found

};

Ответ 6

Бинарный поиск ES6

// bottom-up
function binarySearch (arr, val) {
    let start = 0;
    let end = arr.length - 1;

    while (start <= end) {
        let mid = Math.floor((start + end) / 2);

        if (arr[mid] === val) {
            return mid;
        }
        if (val < arr[mid]) {
            end = mid - 1;
        } else {
            start = mid + 1;
        }
    }
    return -1;
}

другой подход:

// recursive
function binarySearch(arr, val, start = 0, end = arr.length - 1) {
    const mid = Math.floor((start + end) / 2);

    if (val === arr[mid]) {
        return mid;
    }
    if (start >= end) {
        return -1;
    }
    return val < arr[mid]
        ? binarySearch(arr, val, start, mid - 1)
        : binarySearch(arr, val, mid + 1, end);
}

Ответ 7

𝘀𝗽𝗲𝗲𝗱 𝘄𝗮𝗻𝘁 𝘀𝗽𝗲𝗲𝗱? 𝘁𝗵𝗶𝘀 𝘁𝗵𝗶𝘀.

Бинарные поиски, реализованные правильно (без изменения массива, создания копий массива или других нелепостей), имеют среднюю сложность около O (k * log ₂ (n)) (где k - константа, представляющая ненужные издержки). Скажем, у вас есть массив из 1024 элементов, и константа k в этом случае равна 1. При линейном поиске средняя сложность будет O (k * n/2) = O (1 * 1024/2) = O (512). При бинарном поиске сложность O (k * log ₂ (n)) = O (1 * log ₂ (1024)) = O (1 * 10) = O (10) может быть сложной. Теперь предположим, что вы делаете алгоритм линейного поиска на 25% быстрее, а алгоритм двоичного поиска - на 25% быстрее. Теперь k равно 0,75 для обоих алгоритмов. Сложность линейного поиска уменьшается до O (384) (усиление 128 баллов производительности), тогда как двоичный поиск уменьшается до O (7,5) (выигрыш всего 2,5 балла производительности). Этот минимальный выигрыш от оптимизации метода двоичного поиска объясняется тем, что метод двоичного поиска уже очень быстрый. Поэтому любой здравомыслящий человек должен быть более склонен оптимизировать остальную часть своей программы, прежде чем он попытается оптимизировать свой алгоритм двоичного поиска. Тем не менее, я не нормальный человек; таким образом, я оптимизировал функцию бинарного поиска до абсолютных пределов разработки Javascript.

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

const sArr = [0,4,5,6,9,13,14,21,27,44];
document.write(slowestBS(sArr, 14)); // don't use document.write in production

function slowestBS(array, searchedValue, ARG_start, ARG_len){
  // Range of [start, start+len): only start is inclusive. It works
  // similarly to "...".substr(start, len).indexOf(sValue)
  // 'void 0' is shorthand for 'undefined'
  var start = ARG_start |0;
  var len = (ARG_len === void 0 ? (array.length|0)-start : ARG_len) | 0;
  len = len - 1 |0;
  for (let i=0x80000000; i; i >>>= 1) {
    if (len & i) {
      const withoutCurBit = len & ~(i-1);
      if (array[start + withoutCurBit] > searchedValue) {
        len = withoutCurBit - 1 |0;
      }
    }
  }
  if (array[start+len] !== searchedValue) {
    // remove this if-statement to return the next closest
    // element going downwards from the searched-for value
    // OR 0 if the value is less than all values in the
    // array
    return -1 - start - len |0;
  }
  return start + len |0;
}

Ответ 8

Разновидностью этой проблемы является поиск элемента, ближайшего к поиску X если нет точного соответствия.

Для этого мы адаптируем ответ @Alexander Ryzhov так, чтобы он всегда возвращал "точку вставки" = индекс наименьшего из тех элементов, которые больше или равны X

Как только мы получим индекс результата I, мы проверяем элементы в I (который может быть X или больше чем X) и I-1 (который меньше) и выбираем самый близкий из двух. Не забудьте разобраться с крайними случаями!

function binarySearch(a, compare) {
    let le = 0,
        ri = a.length - 1;

    while (le <= ri) {
        let mid = (le + ri) >> 1,
            cmp = compare(a[mid]);

        if (cmp > 0) {
            le = mid + 1;
        } else if (cmp < 0) {
            ri = mid - 1;
        } else {
            return mid;
        }
    }

    return le;
}


function binaryClosest(a, compare) {
    let i = binarySearch(a, compare);

    if (i === 0)
        return a[0];

    if (i === a.length)
        return a[i - 1];

    let d1 = -compare(a[i]),
        d2 = compare(a[i - 1]);

    return d1 < d2 ? a[i] : a[i - 1];
}


//

input = [-3, -2, -1, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 3]
findX = x => binaryClosest(input, item => x - item)

test = (exp, arg) => {
    let x = findX(arg)
    console.log(exp === x ? 'ok' : 'FAIL', arg, exp, x)
};

test(-3, -99)
test(+3, +99)

test(0, +0.3)
test(0, 0)
test(0, -0.3)

test(-1, -1.3)
test(+1, +1.3)

test(2, 2.2)
test(2, 2.3)
test(2, 2.5)
test(3, 2.6)

Ответ 9

Предполагая отсортированный массив, здесь рекурсивный двоичный поиск:

function binSearch(needle, arr) {
  length = arr.length;
  while(length > 1) {
    midpoint = Math.floor(length/2);
    return (needle > arr[midpoint-1]) ? 
           binSearch(needle, arr.splice(midpoint, length)) :    
           binSearch(needle, arr.splice(0, midpoint));
  }
  return needle === arr[0] ? arr[0] : -1;
}

Ответ 10

Вы также должны проверить "крайний край", и сделать его первым базовым условием, после чего следует успешный поиск. Следовательно, вам не нужно проверять длину массивa > 1 при рекурсии через массив. Наконец, поскольку вы не возвращаете массив, почему бы не использовать метод Array.prototype.slice?

var binarySearch = function(arr, val) {
  var half = Math.floor(arr.length / 2);

  if (arr.length === 0) {
    return -1;
  }
  else if (arr[half] === val) {
    console.log("val: ", val, "arr[half]: ", arr[half]);
    return val;
  }
  else if (val > arr[half]) {
    console.log("val: ", val, "arr[half]: ", arr[half]);
    return binarySearch(arr.slice(half, arr.length), val);
  }
  else {
    console.log("val: ", val, "arr[half]: ", arr[half]);
    return binarySearch(arr.slice(0, half), val);
  }
}


var arr = [1, 5, 20, 58, 76, 8, 19, 41].sort(function(a, b) { return a - b });

console.log("Sorted array: " + arr);
console.log(binarySearch(arr, 76));
console.log(binarySearch(arr, 19));
console.log(binarySearch(arr, 0));

Ответ 11

Я хочу добавить функцию searchArray двоичного поиска вместе с функциями утилиты инструментов insertSortedArray и removeSortedArray в список ответов, так как я думаю, что он чист, он пользуется глобальным использованием, и я думаю, что это довольно оптимальная скорость.

Ответ 12

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

function binarySearch(array, target, max, min) {

    //Find the Midpoint between forced max and minimum domain of the array
    var mid = ((max - min) >> 1) + min;
    //alert("Midpoint Number" + mid);
    console.log(mid);
    console.log(array[mid], "target: " + target);

    if (array[mid] === target) {
        //Target Value found
        console.log('match', array[mid], target);
        //alert('match', array[mid], target);
        return mid;
    } 
    else if (mid === 0)
    {
        //All Value have been checked, and none are the target value, return sentinel value
        return -1;
    }
    else if (array[mid] > target)
    {
        //Value at Midpoint is greater than target Value, set new maximum to current midpoint
        max = mid;
        console.log('mid lower', array[mid], target);
        //alert('mid lower', array[mid], target);
        //Call binarySearch with new search domain
        return binarySearch(array, target, max, min);
    } 

    else if (array[mid] < target)
    {
        // Value at Midpoint is less than the target Value, set new minimum to current midpoint
        min = mid;
        console.log('mid higher', array[mid], target);
        //alert('mid higher', array[mid], target);

        //Call binarySearch with new search domain
        return binarySearch(array, target, max, min);
    } 

Я уверен, что здесь есть место для уточнения, но этот метод не позволяет выполнять глубокую копию массива (что может быть дорогостоящим действием при работе с большим набором данных), и в то же время оно не модифицируйте массив любым способом.

Надеюсь, что это поможет! Благодаря, Джереми

Ответ 13

function binarySearch(a = [], x) {
    let length = a.length;
    if (length === 0) {
        return false;
    } else {
        let m = Math.floor(length/2);
        let y = a[m];
        if (x === y) {
            return true;
        } else if (x < y) {
            return binarySearch(a.slice(0, m), x);
        } else {
            return binarySearch(a.slice(m + 1), x);
        }
    }
}

Ответ 14

У меня есть реализация на github с сопоставлением между двоичной и линейной и тестовой страницей, если вам все еще интересно увидеть больше реализаций здесь

Ответ 15

Вот функция ES6 в стиле функционального программирования, которая использует функцию сравнения по умолчанию, если ни один не предоставил: если значение, которое требуется для поиска, относится к типу числа, предполагается числовое сравнение, в противном случае сравнение строк.

function binarySearch(arr, val, compFunc = 
    (a, b) => typeof val == 'number' ? a-b : a.localeCompare(b), i=0, j=arr.length) {
  return i >= j ? i
    : ( mid =>
          ( cmp => 
              cmp < 0 ? binarySearch(arr, val, compFunc, i, mid) 
            : cmp > 0 ? binarySearch(arr, val, compFunc, mid+1, j) 
            : mid 
          ) (compFunc(val, arr[mid]))
      ) (i + j >> 1);
}

///////// Tests ///////////////////

function check(arr, val, compFunc) {
  var fmt = JSON.stringify;
  var result = binarySearch(arr, val); // default compFunc is assumed
  console.log(`binarySearch(${fmt(arr)}, ${fmt(val)}) == ${fmt(result)}`);
  if (result > arr.length || result < 0 || !arr.length && result 
    || result < arr.length && compFunc(val, arr[result]) > 0
    || result > 0 && compFunc(val, arr[result-1]) < 0) throw "Unexpected result!!!"
}

// Tests with numeric data:
for (var val = 0; val < 12; val++)      
  check([1, 2, 4, 6, 9, 9, 10], val, (a,b) => a-b);
// Test with empty array:
check([], 12, (a,b) => a-b);
// Test with string data:
check(['abc', 'deaf', 'def', 'g'], 'dead', (a, b) => a.localeCompare(b));

Ответ 16

Это рекурсивный, он должен корректно работать везде.

    //  It compares the target value to the middle element of the array; if they are
    //  unequal, the half in which the target cannot lie is eliminated and the search continues
    //  on the remaining half until it is successful.
    //
    Array.prototype.binSearch = function(search, start, end) {

        // shortcircuit to initialize parameters
        //
        start = start || 0;
        end = end || this.length;

        // this is the middlepoint between
        // the lowest and highest portion of the
        // array
        //
        var ind = Math.floor(end + start) / 2;

        // returns an error if there nothing
        // to search
        //
        if(!search) return "Nothing to search";

        // this is where the recursion stop
        // stops because the element
        // has been found
        //
        if(this[ind] == search)
            return ind;

        // this checks if the element is smaller
        // than the search argument
        //
        else if(this[ind] < search)

            // returns the function with the middlepoint
            // as the lowest portion of the array
            //
            return this.binSearch(search, ind, end);
        else


            // returns the function with the middlepoint
            // as the highest portion of the array
            //
            return this.binSearch(search, start, ind);
    }

    console.log([1,33,44,55,89,101,1023,3245].binSearch(101)); // 5
    console.log([1,33,44,55,89,101,1023,3245].binSearch(33)); // 1

Ответ 17

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

Прежде всего, BinarySearch - это алгоритм, который в O (log (n)) в массиве отсортирован находит индекс, в который мы можем вставить наш элемент и все еще иметь отсортированный массив ( мы можем использовать его также для поиска ближайшего элемента - поэтому, чтобы ответить на какой-то вопрос в комментариях, есть смысл вернуть значение - это может быть другое значение из того, что вы запрашиваете)

В реализации splice наблюдается серьезный отказ в разработке - алгоритм поиска изменяет запрашиваемый массив. Представьте, что у вас есть база данных, и вы запрашиваете SELECT * FROM data WHERE id=1, а половина вашей таблицы удаляется. Клонирование массива перед переходом к BinarySearch не очень полезно, но я объясню, почему в следующем параграфе.

Итак, давайте исправить эту ошибку проектирования и использовать новую функцию slice, которая будет работать так же, как splice, но не будет изменять массив (просто вернуть выбранные элементы). В алгоритме по-прежнему существует большая ошибка. Для массива n=2^m мы делаем тесты m. Сначала мы возвращаемся из slice n/2 элементов, в следующий раз n/4, затем n/8 и так далее. Если подвести итог, это будут элементы n-1. Таким образом, у нас есть алгоритм O(n), и он выполняется так же быстро, как и линейный, но гораздо сложнее (линейный поиск еще быстрее, поскольку его средняя стоимость n/2 и slice BinarySearch - это aways n-1). Оригинальная реализация splice еще хуже - каждому splice потребуется дополнительно перемещать элементы в таблице, поэтому в худшем случае первый раз это будет n second n/2 third n/4, поэтому в итоге это будет 2 * n - 1 - и поэтому массив клонирования не очень полезен (клонирование - это O(n), поэтому никогда не клонируйте свой массив, прежде чем перейти к алгоритму бинарного поиска хорошего)

Ответ 18

function binarySearch(arr, num, l, r){
	if( arr instanceof Array ){
  	
    l = isNaN(l) ? 0 : l;
    r = isNaN(r) ? arr.length - 1: r;
    let mid = l + 1 + Math.round((r - l)/2 - 1);    
    console.log(l, r, mid, arr[mid]);
    
    if( num == arr[mid] ){ 
    	console.log("found"); 
      return mid; 
    }
    
    if( typeof arr[mid] == "undefined" || l == r ){
    	console.log("not found"); return -1;
    }
    
    if( num < arr[mid] ){  
    	console.log("take left"); 
      return binarySearch(arr, num, l, r - mid);
    }
    
    console.log("take right");
    return binarySearch(arr, num, mid, r);
    
  }
}

console.log( binarySearch([0, 0, 1 ,1, 2, 3, 5, 6, 11], 2) );

Ответ 19

Предположим, что массив отсортирован (либо напишите собственный собственный алгоритм, либо просто используйте встроенные методы)

function bSearch(array,item){
  var start = 0,
  end = item.length - 1;
  var middle = Math.floor((end+start)/2);
  while(array[middle] !== item && start < end){
    if(item < array[middle]){
      end = middle-1;
     }
    else if(item > array[middle]){
      start = middle+1;
     }
     middle = Math.floor((end+start)/2);

  } 
  if(array[item]!== middle){
     console.log('notFoundMate);
     return -1;
  }
  else {
     console.log('FoundMate);
     return middle;
  }
}

Ответ 20

Просто проверьте lodash реализация здесь

Ответ 21

чтобы использовать его, просто скопируйте и вставьте его как есть, чтобы использовать локальные переменные для скорости. и измените искомое значение, например, если вы ищете в подобъектах или массивах:

if (array[mid][0] < value[0]) low = mid + 1;
if (array[mid].val < value.val) low = mid + 1;

для более быстрых результатов используйте массивы или массивы массивов или параллельные массивы, скопируйте искомые массивы в локальные переменные. нелокальные переменные или каждый раз, когда вы делаете obj.something, это замедляется.

это самая быстрая версия, как это:

let array=[3,4,5,6]
let value=5; //searched value
let mid, low = 0,high = array.length;
while (low < high) {
    mid = low + high >>> 1; // fast divide by 2 and round down
    if (array[mid] < value) low = mid + 1;
    else high = mid;
}
//if (array[mid] != value) mid=-1;// this might not be required if you look for place to insert new value
mid;// contains the found value position or if not found one before where it would be if it was found

бинарный поиск работает так:

|           .           |     // find middle
//option 1:
|           .     v     |     // if value on right, middle is top
            |     .     |     // so then it is like this
//option 2:                    
|     v     .           |     // if value on left, middle is bottom
|     .     |                 // so then it is like this
//more loops of option 2 until not found
|  .  |                       // next time it will be like this
|. |                          // next time it will be like this
.                             // next time it will be like this

эта реализация идет ко дну, если не найдена. это можно найти или не найти всегда. возвращает индекс ниже или равен искомому значению. так что вам нужно проверить, равно ли оно. проверить, существует ли значение или это только один результат ниже. если вы ищете место для вставки inn order, просто поставьте его в этом месте, не нужно проверять, равно ли оно

Ответ 22

Я думаю, что ниже вариант прост в реализации бинарного поиска в JS.

arr = [1,2,3,4,5];
searchTerm=2;
function binarySearchInJS(start,end)
{
    isFound=false;
    if(end > start)
    {
        //console.log(start+"\t"+end)
        mid =  (end+start)/2;

        mid = Math.floor(mid)

        if(searchTerm==arr[mid])
        {                   
              isFound = true;             
        }
        else
        {   

            if(searchTerm < arr[mid])
            {               
                binarySearchInJS(start,mid);
            }
            if(searchTerm > arr[mid])
            {           
                binarySearchInJS(mid+1,end);
            }
        }
    }

    if(isFound)
    {
        return "Success";   
    }
    else{
            return "Not Found"; 
    }       
}

Ответ 23

Полнофункциональный бинарный поиск:

• Отрицательное значение указывает точку вставки
• Разрешить поиск первого и последнего индекса
• начальный индекс, эксклюзивный конечный индекс
• Пользовательская функция сравнения

(этот код и unit тест здесь)

function defaultCompare(o1, o2) {
    if (o1 < o2) {
        return -1;
    }
    if (o1 > o2) {
        return 1;
    }
    return 0;
}

/**
 * @param array sorted array with compare func
 * @param item search item
 * @param start (optional) start index
 * @param end (optional) exclusive end index
 * @param compare (optional) custom compare func
 * @param bound (optional) (-1) first index; (1) last index; (0) doesn't matter
 */
function binarySearch(array, item, start, end, compare, bound) {
    if (!compare) {
        compare = defaultCompare;
    }
    let from = start == null ? 0 : start;
    let to = (end == null ? array.length : end) - 1;
    let found = -1;
    while (from <= to) {
        const middle = (from + to) >>> 1;
        const compareResult = compare(array[middle], item);
        if (compareResult < 0) {
            from = middle + 1;
        }
        else if (compareResult > 0) {
            to = middle - 1;
        }
        else if (!bound) {
            return middle;
        }
        else if (bound < 0) {
            // First occurrence:
            found = middle;
            to = middle - 1;
        }
        else {
            // Last occurrence:
            found = middle;
            from = middle + 1;
        }
    }
    return found >= 0 ? found : -from - 1;
}

Ответ 24

Давайте рассмотрим элегантный рекурсивный пример с хвостовыми вызовами, который влияет на производительность большинства браузеров, поддерживающих стандарт ES6:

function binarySearch(arr, item) {
  function search(low, high) {
    if (low > high) return -1
    const mid = Math.floor((low + high)/2)
    if (arr[mid] === item) return mid
    const nextLow = item > arr[mid] ? mid+1 : low
    const nextHigh = item < arr[mid] ? mid-1 : high
    return search(nextLow, nextHigh)
  }
  return search(0, arr.length-1)
}

Положительные тесты:

binarySearch([2, 6, 9, 14, 21],  9) // => 2
binarySearch([2, 6, 9, 14, 21], 21) // => 4
binarySearch([2, 6, 9, 14, 21],  2) // => 0

Отрицательные тесты:

binarySearch([2, 6, 9, 14, 21],  0) // => -1
binarySearch([2, 6, 9, 14, 21], -4) // => -1
binarySearch([2, 6, 9, 14, 21], 40) // => -1

Ответ 25

Вы не можете использовать двоичный поиск для несортированного массива. вы должны иметь [1, 4, 13, 77...], но не [1, 2, 13, 5, 17...] ... мой плохой, вы сделали сортировку()