javascript

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

  • пятница, 29 декабря 2023 г. в 00:00:21
https://habr.com/ru/articles/783848/

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

Нам нужно написать функцию, которая принимает отсортированный массив чисел 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.