Двоичный поиск

Описание

• Википедия
• YouTube
• GitHub

Двоичный (бинарный) поиск (метод деления пополам или дихотомия) (binary/half-interval/logarithmic search, binary chop) -это классический алгоритм поиска элемента в отсортированном массиве (векторе), использующий дробление массива на половины. Суть такая: мы сравниваем целевое значение с центральным элементом массива. Если они неравны, половина, в которой точно нет целевого значения, отбрасывается, и поиск продолжается в другой половине по такому же принципу. Если поиск завершился пустым массивом, значит, целевое значение в массиве отсутствует.

Временная сложность алгоритма составляет O(log(n)), поскольку мы уменьшаем площадь поиска вдвое на каждой итерации.

Реализация

// algorithms/searches/binary-search.js
import Comparator from '../../utils/comparator'

export default function binarySearch(sortedArr, target, fn) {
  const comparator = new Comparator(fn)

  let start = 0
  let end = sortedArr.length - 1

  while (start <= end) {
    // Вычисляем индекс центрального элемента
    let middle = start + Math.floor((end - start) / 2)

    if (comparator.equal(sortedArr[middle], target)) {
      return middle
    }

    // Если целевое значение меньше центрального элемента
    if (comparator.lessThan(sortedArr[middle], target)) {
      // Переходим к правой половине массива
      start = middle + 1
    } else {
      // Переходим к левой половине массива
      end = middle - 1
    }
  }

  return -1
}

Тестирование

// algorithms/searches/__tests__/binary-search.test.js
import binarySearch from '../binary-search'

describe('binarySearch', () => {
  it('должен найти числа в отсортированных массивах', () => {
    expect(binarySearch([], 1)).toBe(-1)
    expect(binarySearch([1], 1)).toBe(0)
    expect(binarySearch([1, 2], 1)).toBe(0)
    expect(binarySearch([1, 2], 2)).toBe(1)
    expect(binarySearch([1, 5, 10, 12], 1)).toBe(0)
    expect(binarySearch([1, 5, 10, 12, 14, 17, 22, 100], 17)).toBe(5)
    expect(binarySearch([1, 5, 10, 12, 14, 17, 22, 100], 1)).toBe(0)
    expect(binarySearch([1, 5, 10, 12, 14, 17, 22, 100], 100)).toBe(7)
    expect(binarySearch([1, 5, 10, 12, 14, 17, 22, 100], 0)).toBe(-1)
  })

  it('должен найти объекты в отсортированном массиве', () => {
    const sortedArrayOfObjects = [
      { key: 1, value: 'value1' },
      { key: 2, value: 'value2' },
      { key: 3, value: 'value3' },
    ]

    const comparator = (a, b) => {
      if (a.key === b.key) return 0
      return a.key < b.key ? -1 : 1
    }

    expect(binarySearch([], { key: 1 }, comparator)).toBe(-1)
    expect(binarySearch(sortedArrayOfObjects, { key: 4 }, comparator)).toBe(-1)
    expect(binarySearch(sortedArrayOfObjects, { key: 1 }, comparator)).toBe(0)
    expect(binarySearch(sortedArrayOfObjects, { key: 2 }, comparator)).toBe(1)
    expect(binarySearch(sortedArrayOfObjects, { key: 3 }, comparator)).toBe(2)
  })
})

Запускаем тестирование:

npm run test ./algorithms/searches/__tests__/binary-search

Результат:

Такие варианты двоичного поиска предлагают разработчики VSCode:

// https://github.com/microsoft/vscode/blob/main/src/vs/base/common/arrays.ts#L73
export function binarySearch(array, key, comparator) {
	return binarySearch2(array.length, i => comparator(array[i], key));
}

export function binarySearch2(length, compareToKey) {
	let low = 0,
		high = length - 1;

	while (low <= high) {
		const mid = ((low + high) / 2) | 0;
		const comp = compareToKey(mid);
		if (comp < 0) {
			low = mid + 1;
		} else if (comp > 0) {
			high = mid - 1;
		} else {
			return mid;
		}
	}
	return -(low + 1);
}

// Тоже самое, но в форме одной функции
// https://github.com/microsoft/vscode/blob/main/extensions/html-language-features/server/src/utils/arrays.ts#L60
export function binarySearch(array, key, comparator) {
	let low = 0,
		high = array.length - 1;

	while (low <= high) {
		const mid = ((low + high) / 2) | 0;
		const comp = comparator(array[mid], key);
		if (comp < 0) {
			low = mid + 1;
		} else if (comp > 0) {
			high = mid - 1;
		} else {
			return mid;
		}
	}
	return -(low + 1);
}