Шаг 1

Чуть упростим задачу поиска. Теперь будем не возвращать индекс искомого элемента, а лишь говорить, присутствует элемент или нет (этакий оптимизированный includes на сортированном массиве). Попробуйте самостоятельно переписать бинарный поиск по новым условиям и с помощью рекурсии.

import {test} from './tester';

/*
Примеры:
binarySearch([], 3) // false
binarySearch([3], 3) // true
binarySearch([1, 2, 3, 4, 5], 4) // true
binarySearch([1, 2, 3, 5, 6], 4) // false
*/

function binarySearch(array, element) {
  return false;
}

test(binarySearch([], 3), false);
test(binarySearch([3], 3), true);
test(binarySearch([1, 2, 3, 4, 5], 4), true);
test(binarySearch([1, 2, 3, 5, 6], 4), false);

Шаг 2

Очевидно, что базовый случай у этой задачи — поиск в массиве из одного элемента. Если он является нашим искомым элементом — возвращаем true, иначе — false. Если массив пустой, искать тоже не стоит — просто вернём false.

import {test} from './tester';

/*
Примеры:
binarySearch([], 3) // false
binarySearch([3], 3) // true
binarySearch([1, 2, 3, 4, 5], 4) // true
binarySearch([1, 2, 3, 5, 6], 4) // false
*/

function binarySearch(array, element) {
  if (array.length === 0) {
    return false;
  }

  if (array.length === 1) {
    return array[0] === element;
  }

  return false;
}

test(binarySearch([], 3), false);
test(binarySearch([3], 3), true);
test(binarySearch([1, 2, 3, 4, 5], 4), true);
test(binarySearch([1, 2, 3, 5, 6], 4), false);

Шаг 3

А теперь начинаем выделять из этой задачи подзадачи — делим наш массив пополам.

import {test} from './tester';

/*
Примеры:
binarySearch([], 3) // false
binarySearch([3], 3) // true
binarySearch([1, 2, 3, 4, 5], 4) // true
binarySearch([1, 2, 3, 5, 6], 4) // false
*/

function binarySearch(array, element) {
  if (array.length === 0) {
    return false;
  }

  if (array.length === 1) {
    return array[0] === element;
  }

  const middle = Math.floor(array.length / 2);

  return false;
}

test(binarySearch([], 3), false);
test(binarySearch([3], 3), true);
test(binarySearch([1, 2, 3, 4, 5], 4), true);
test(binarySearch([1, 2, 3, 5, 6], 4), false);

Шаг 4

И запускаем подзадачу поиска в нужной нам части массива! Определять нужную часть массива мы уже научились в прошлой главе.

  import {test} from './tester';

/*
Примеры:
binarySearch([], 3) // false
binarySearch([3], 3) // true
binarySearch([1, 2, 3, 4, 5], 4) // true
binarySearch([1, 2, 3, 5, 6], 4) // false
*/

function binarySearch(array, element) {
  if (array.length === 0) {
    return false;
  }

  if (array.length === 1) {
    return array[0] === element;
  }

  const middle = Math.floor(array.length / 2);

  if (array[middle] > element) {
    return binarySearch(array.slice(0, middle), element)
  }

  return binarySearch(array.slice(middle + 1), element)
}

test(binarySearch([], 3), false);
test(binarySearch([3], 3), true);
test(binarySearch([1, 2, 3, 4, 5], 4), true);
test(binarySearch([1, 2, 3, 5, 6], 4), false);

Шаг 5

На самом деле, мы потеряли ещё один базовый случай: если в середине уже лежит искомый нам элемент, нам не нужно создавать подзадачи, просто будем возвращать true.

  import {test} from './tester';

/*
Примеры:
binarySearch([], 3) // false
binarySearch([3], 3) // true
binarySearch([1, 2, 3, 4, 5], 4) // true
binarySearch([1, 2, 3, 5, 6], 4) // false
*/

function binarySearch(array, element) {
  if (array.length === 0) {
    return false;
  }

  if (array.length === 1) {
    return array[0] === element;
  }

  const middle = Math.floor(array.length / 2);

  if (array[middle] === element) {
    return true;
  }

  if (array[middle] > element) {
    return binarySearch(array.slice(0, middle), element)
  }

  return binarySearch(array.slice(middle + 1), element)
}

test(binarySearch([], 3), false);
test(binarySearch([3], 3), true);
test(binarySearch([1, 2, 3, 4, 5], 4), true);
test(binarySearch([1, 2, 3, 5, 6], 4), false);

Шаг 6

Здесь довольно хорошо видно, что рекурсивные решения проще для понимания относительно итеративных. Вместо манипуляций с указателями мы просто запускаем поиск по нужной части внутри основной задачи. Использование рекурсии и подхода «Разделяй и властвуй» — зачастую не единственный, но самый выразительный способ понятно донести свои мысли в код.

 import {test} from './tester';

/*
Примеры:
binarySearch([], 3) // false
binarySearch([3], 3) // true
binarySearch([1, 2, 3, 4, 5], 4) // true
binarySearch([1, 2, 3, 5, 6], 4) // false
*/

function binarySearch(array, element) {
  if (array.length === 0) {
    return false;
  }

  if (array.length === 1) {
    return array[0] === element;
  }

  const middle = Math.floor(array.length / 2);

  if (array[middle] === element) {
    return true;
  }

  if (array[middle] > element) {
    return binarySearch(array.slice(0, middle), element)
  }

  return binarySearch(array.slice(middle + 1), element)
}

test(binarySearch([], 3), false);
test(binarySearch([3], 3), true);
test(binarySearch([1, 2, 3, 4, 5], 4), true);
test(binarySearch([1, 2, 3, 5, 6], 4), false);

File tester.js

const results = document.getElementById('results')

export function test(left, right) {
  const result = document.createElement('li');

  if (left === right) {
    result.innerHTML = "Тест пройден!";
    result.style.color = "green";
  } else {
    result.innerHTML = `Тест не пройден! ${left} не равно ${right}`;
    result.style.color = "red";
  }

  results.appendChild(result);
}