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

Условия задачи

Нам нужно написать функцию, которая принимает отсортированный массив чисел numberArray и возвращает индекс найденного числа. Если индекс не найден, тогда возвращается -1.

Сразу уделю внимание на то, что длинна массива может быть любой. Массив может состоять из любых чисел и искомое число так же может быть любым.

Предположим у нас есть массив чисел от 1 до 100:

const numberArray [    1,  2,  3,   4,  5,  6,  7,  8,  9, 10, 11, 12,   13, 14, 15,  16, 17, 18, 19, 20, 21, 22, 23, 24,   25, 26, 27,  28, 29, 30, 31, 32, 33, 34, 35, 36,   37, 38, 39,  40, 41, 42, 43, 44, 45, 46, 47, 48,   49, 50, 51,  52, 53, 54, 55, 56, 57, 58, 59, 60,   61, 62, 63,  64, 65, 66, 67, 68, 69, 70, 71, 72,   73, 74, 75,  76, 77, 78, 79, 80, 81, 82, 83, 84,   85, 86, 87,  88, 89, 90, 91, 92, 93, 94, 95, 96,   97, 98, 99, 100 ]

Линейный поиск

Начнем с определения.

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

Напишем функцию, которая будет проверять все элементы массива по очереди:

const linearSearch = (numbersArray, targetNumber) => {   for (let i = 0; i < numbersArray.length; i++) {     if (numbersArray[i] === targetNumber) {       return i // Элемент найден     }   }      return -1; // Элемент не найден }

Если в качестве targetNumber мы передадим 1, тогда нам потребуется одна итерация цикла, чтобы найти число.

Если в качестве targetNumber мы передадим 100, тогда нам потребуется 100 итераций цикла, чтобы найти число.

В данном алгоритме сложность O(n). Такую сложность так же называют линейной сложностью.

Такой поиск крайне не эффективный при работе с большим набором данных.

Бинарный поиск гораздо более эффективный в сравнении с линейным поиском.

Бинарный поиск основан на идее деления данных на половины и последующем поиске в одной из них с последующим делением.

Принцип бинарного поиска

Предположим, что в нашем отсортированном списке чисел от 1 до 100 мы будем искать число 87.

Первое действие:

Разделим наш массив пополам. У нас получилось 2 массива one и two. В one числа от 1 до 50, а в two с 51 до 100.

const one = [   1,  2,  3,   4,  5,  6,  7,  8,  9, 10,    11, 12, 13, 14, 15,  16, 17, 18, 19, 20,    21, 22, 23, 24, 25, 26, 27,  28, 29, 30,   31, 32, 33, 34, 35, 36, 37, 38, 39,  40,    41, 42, 43, 44, 45, 46, 47, 48, 50 ]  const two = [   51,  52, 53, 54, 55, 56, 57, 58, 59, 60,   61, 62, 63,  64, 65, 66, 67, 68, 69, 70,   71, 72, 73, 74, 75,  76, 77, 78, 79, 80,   81, 82, 83, 84, 85, 86, 87,  88, 89, 90,   91, 92, 93, 94, 95, 96, 97, 98, 99, 100 ]

Посмотрим последний элемент массива one. 49 больше, чем 87? Нет.
Тогда смотрим последний элемент массива two. 100 больше, чем 87? Да, значит искать число будет массиве two. При первом действии мы уже отсекли половину данных.

Второе действие:

Массив two снова раздели на два. Получаем массив three c числами от 50 до 75 и four с числами от 76 до 100.

const three = [   50, 51,  52, 53, 54, 55, 56, 57, 58, 59, 60,   61, 62, 63,  64, 65, 66, 67, 68, 69, 70, 71,   72, 73, 74, 75  ]  const four = [   76, 77, 78, 79, 80, 81, 82, 83, 84, 95, 85,   86, 87,  88, 89, 90, 91, 92, 93, 94, 96, 97,   98, 99, 100 ]

Посмотрим последний элемент массива three. 75 больше, чем 87? Нет.
Тогда смотрим последний элемент массива four. 100 больше, чем 87? Да, значит искать число будет в массиве four. При втором действии мы отсекли еще половину данных.

Третье действие:

Массив four снова раздели на два. Получаем массив five с числами от 76 до 87 и массив six с числами от 88 до 100.
```
const five = [   76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87,  ]  const six = [   88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100 ]
```
Посмотрим последний элемент массива five.
87 больше, чем 87? Нет. Они равны. Мы нашли наше число на третьем действии.

Алгоритм бинарного поиска

Бинарный поиск работает только в том случае, если список отсортирован!

По условию задачи у нас может быть любая длинна массива и любые отсортированные числа в начале массива.

Напишем решение для нашей задачи с использованием бинарного поиска.

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

Напишем функцию getRandomNumber, которая возвращает рандомное число в заданном диапазоне:

const getRandomNumber = (min, max) => {   // Метод Math.ceil() - округление вверх. Округляет аргумент до ближайшего большего целого.   min = Math.ceil(min);   // Метод Math.floor() - округление вниз. Округляет аргумент до ближайшего меньшего целого.   max = Math.floor(max);    // Максимум не включается, минимум включается   return Math.floor(Math.random() * (max - min) + min); }

Напишем функцию createRandomNumberArray, которая возвращает массив чисел заданной длинны с отсортированными числами.

const createRandomNumberArray = (arrayLength, firstNumber) => {   return Array.from({ length: arrayLength }, (_, index) => index + firstNumber); }

Далее напишем функцию binarySearch, которая будет возвращать объект с найденным индексом (или -1) и с количеством итераций цикла, которые мы прошли.

const binarySearch = (numbersArray, targetNumber) => {   let left = 0;   let right = numbersArray.length - 1;   let foundIndex = -1   let operations = 0      while (left <= right) {     const mid = Math.floor((left + right) / 2);          if (numbersArray[mid] === targetNumber) {       foundIndex = mid; // Элемент найден       break;     } else if (numbersArray[mid] &lt; targetNumber) {       left = mid + 1; // Ищем в правой половине     } else {       right = mid - 1; // Ищем в левой половине     }        operations += 1   }      return { foundIndex, operations } }

Так же напишем функцию linearSearch c обычным линейным поиском, которая будет возвращать объект с найденным индексом или -1 и с количеством итераций цикла, которые мы прошли.

const linearSearch = (numbersArray, targetNumber) => {   let foundIndex = -1   let operations = 0    for (let i = 0; i < numbersArray.length; i++) {     if (numbersArray[i] === targetNumber) {       foundIndex = i       return { foundIndex, operations }; // Элемент найден     }          operations += 1   }    return { foundIndex, operations }; // Элемент не найден }

Получим следующие данные:

// Случайная длина массива const arrayLength = getRandomNumber(1000, 2000) // Случайное число с которого будут начинаться наши числа. const firstNumber = getRandomNumber(1, 1000) // Случайное число, которое мы будем искать const targetNumber = getRandomNumber(firstNumber, 1000)

И наконец-то создадим сам массив:

// Массив чисел const numbersArray = createRandomNumberArray(arrayLength, firstNumber)

И в конце будем запускать наш код и сравним количество итераций цикла в функции и функции:

const binaryResult = binarySearch(numbersArray, targetNumber) const linearResult = linearSearch(numbersArray, targetNumber)  console.log('arrayLength', arrayLength) console.log('firstNumber', firstNumber) console.log('targetNumber', targetNumber) console.log('binaryResult', binaryResult) console.log('linearResult', linearResult)

Полная версия кода:

const getRandomNumber = (min, max) => {   // Метод Math.ceil() - округление вверх. Округляет аргумент до ближайшего большего целого.   min = Math.ceil(min);   // Метод Math.floor() - округление вниз. Округляет аргумент до ближайшего меньшего целого.   max = Math.floor(max);    // Максимум не включается, минимум включается   return Math.floor(Math.random() * (max - min) + min); }  const createRandomNumberArray = (arrayLength, firstNumber) => {   return Array.from({ length: arrayLength }, (_, index) => index + firstNumber); }  const binarySearch = (numbersArray, targetNumber) => {   let left = 0;   let right = numbersArray.length - 1;   let foundIndex = -1   let operations = 0      while (left <= right) {     const mid = Math.floor((left + right) / 2);          if (numbersArray[mid] === targetNumber) {       foundIndex = mid; // Элемент найден       break;     } else if (numbersArray[mid] &lt; targetNumber) {       left = mid + 1; // Ищем в правой половине     } else {       right = mid - 1; // Ищем в левой половине     }        operations += 1   }      return { foundIndex, operations } }  const linearSearch = (numbersArray, targetNumber) => {   let foundIndex = -1   let operations = 0    for (let i = 0; i < numbersArray.length; i++) {     if (numbersArray[i] === targetNumber) {       foundIndex = i       return { foundIndex, operations }; // Элемент найден     }          operations += 1   }    return { foundIndex, operations }; // Элемент не найден }  // Случайная длина массива const arrayLength = getRandomNumber(1000, 2000) // Случайное число с которого будут начинаться наши числа. const firstNumber = getRandomNumber(1, 1000) // Случайное число, которое мы будем искать const targetNumber = getRandomNumber(firstNumber, 1000)  // Массив чисел const numbersArray = createRandomNumberArray(arrayLength, firstNumber)  const binarySearch = (numbersArray, targetNumber) => {   let left = 0;   let right = numbersArray.length - 1;   let foundIndex = -1   let operations = 0      while (left <= right) {     const mid = Math.floor((left + right) / 2);          if (numbersArray[mid] === targetNumber) {       foundIndex = mid; // Элемент найден       break;     } else if (numbersArray[mid] &lt; targetNumber) {       left = mid + 1; // Ищем в правой половине     } else {       right = mid - 1; // Ищем в левой половине     }        operations += 1   }      return { foundIndex, operations } }  const binaryResult = binarySearch(numbersArray, targetNumber) const linearResult = linearSearch(numbersArray, targetNumber)  console.log('arrayLength', arrayLength) console.log('firstNumber', firstNumber) console.log('targetNumber', targetNumber) console.log('binaryResult', binaryResult) console.log('linearResult', linearResult)

Смотрим консоль с результатами выполнения:

arrayLength 1376 firstNumber 499 targetNumber 995 binaryResult { foundIndex: 496, operations: 9 } linearResult { foundIndex: 496, operations: 496 }

arrayLength 1158 firstNumber 785 targetNumber 817 binaryResult { foundIndex: 32, operations: 8 } linearResult { foundIndex: 32, operations: 32 }

arrayLength 1002 firstNumber 671 targetNumber 822 binaryResult { foundIndex: 151, operations: 7 } linearResult { foundIndex: 151, operations: 151 }

arrayLength 1235 firstNumber 951 targetNumber 970 binaryResult { foundIndex: 19, operations: 9 } linearResult { foundIndex: 19, operations: 19 }

arrayLength 1599 firstNumber 649 targetNumber 940 binaryResult { foundIndex: 291, operations: 10 } linearResult { foundIndex: 291, operations: 291 }

В этих пяти случаях:

Для бинарного поиска потребовалось от 7 до 10 итераций цикла.
Для линейного поиска потребовалось от 19 до 496 итераций цикла.

Для линейного поиска максимальное количество итераций совпадает с размером массива.

С бинарным поиском дело обстоит иначе. Если список состоит из 100 элементов, потребуется не более 7 попыток. Для списка из 4 миллиардов элементов потребуется не более 32 попыток. Впечатляет, верно?

Бинарный поиск выполняется за логарифмическое время и имеет сложность O(log n).

Логарифмы

Логарифм — это математическая функция, которая говорит нам, сколько раз нужно умножить определенное число (называемое основанием логарифма) на само себя, чтобы получить другое число.

Давай представим, что у нас есть число 1000. Если мы возьмем логарифм числа 1000 по основанию 10, результат будет 3. Это означает, что 10 умноженное на себя три раза (10 * 10 * 10) равно 1000.

Логарифм − операция, обратная возведению в степень.

В нашем случае log всегда означает log по основанию 2.

Для бинарного поиска в худшем случае потребуется не более log n проверок.

Для списка из 8 элементов log 8 потребуется не более 3 проверок, потому что 2^3 = 8.

Для списка из 1024 элементов log 1024 не более 10 проверок, потому что 2^10 = 1024.

ссылка на оригинал статьи https://habr.com/ru/articles/783848/

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

Условия задачи

Линейный поиск