Узнать о бинарном поиске

структура данных

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

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

Советы:Данные должны быть упорядочены, то есть отсортированы.

не знаю? Это не имеет значения, позвольте мне объяснить это простым и понятным способом.

Давайте сначала посмотрим на массив:

let arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Если я хочу найти индекс шестого числа 5, как мне его найти? Это не ерунда...

let target = 5;

for(let i = 0, len = arr.length; i < len; i++){

      if(arr[i] == target){

            return i;

      }

}

Затем мы анализируем этот код, предполагая, что длина массива N, нам нужно найти N раз, времяСложность O(n). Что если количество данных велико? 100, 1000, 10000; даже 100 000 больше. Сложность времени увеличивается линейно? Это где бинарный поиск пригодится.

Основная идея бинарного поиска

Советы: поскольку данные отсортированы, мы можем это сделать. (Индекс медианы здесь представлен серединой)

1 с двумя указателями, одна указывая на первый номер, левый = 0, указатель на последний номер, справа = ARR.LINGHING - 1

2. Затем возьмите медиану, чтобы определить размер медианы arr[mid] и целевое значение target

3. Если медиана просто нужно найти этот номер, индекс возвращается непосредственно в Mid, если оно больше целевого значения?，肯定在中位数的后面，即 mid+1 到数组的最后一位。 так,

let target = 5;
let left = 0
let right = arr.length - 1;
while(left <= right){
   let mid = Math.floor((right + left) / 2)
   if(arr[mid] === target){     //找到目标值
      return mid; 
   }else if(arr[mid] > target){ //比目标值大，说明数在前半部分，缩小右边界
      right = mid - 1;
   }else{                       //比目标值小，说明数在后半部分，缩小左边界
      left = mid + 1; 
   }
}

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

Передовые идеи бинарного поиска

левая граница

Теперь мы изменим массив, чтобы он выглядел так

let arr = [0, 1, 2, 3, 4, 5, 5, 5, 6, 7, 8, 9]

или вот так

let arr = [0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 4, 5, 5, 5, 6, 7, 8, 9]

или

let arr = [........ этот массив очень длинный, что является очень большим значением]


第1趟的左边界： 0
第2趟中间值： 8
第3趟的右边界： 17
----------------------------------
第4趟的左边界： 9
第5趟中间值： 13
第6趟的右边界： 17
----------------------------------
13


第1趟的左边界： 0
第2趟中间值： 8
第3趟的右边界： 17
----------------------------------
第4趟的左边界： 9
第5趟中间值： 13
第6趟的右边界： 17
----------------------------------
第4趟的左边界： 9
第5趟中间值： 13
第6趟的右边界： 17
----------------------------------
第4趟的左边界： 9
第5趟中间值： 13
第6趟的右边界： 17
----------------------------------
第4趟的左边界： 9
第5趟中间值： 13
第6趟的右边界： 17
----------------------------------
11

Правая граница


       На самом деле, пусть mid = left + (right - left)/2 Когда правое большое, а левое отрицательное и маленькое, правое - левое может превышать максимальное значение, которое может быть представлено типом int, но в целом левое и правое представляют значение индекса массива, а значение left неотрицательно, поэтому вероятность переполнения справа налево невелика. 

Мы рекомендуем следующие два способа написания

let mid = (left + right) >>> 1 ;
let mid = left + (right - left) / 2;

На самом деле не надо так заморачиваться, можно писать напрямую, блокировать интервал в [Left, Right], неизбежно будет одно просто первое равно целевому значению, а другое не равно до целевого значения. Прямой просмотр кода и комментариев.


Соответственно, оптимизируем код


Суммировать

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

Вот онлайн-шаблон, который на самом деле просто предложение.Левый плюс правый, а не плюс, ищите правое, чтобы уменьшить левое, ищите левое, чтобы уменьшить правое.Вы можете подумать, почему?


Описание шаблона:

Во-первых, формулировка и основа для приведенного выше шаблона, написание только основы для поиска значения, условие прекращения правильно! = Влево, а диапазон поиска — [влево, вправо], когда [2,3] или [3,2] время завершит цикл. Таким образом, то мы должны сделать больше, чтобы определить, когда равны, слишком много условий суждения.

Поиск левых границ: поскольку он остается закрытым, когда MID является целевым значением, правая граница сжимается, позволяя целевому значению максимально сместиться влево.

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

Для более подробной информации, пожалуйста, перейдите по ссылке:Lee TCO's-talent.com/explore/


Категории