Binary search

Binary search

Task conditions

We need to write a function that accepts a sorted array of numbers numberArray and returns the index of the number found. If the index is not found, then is returned -1.

I will immediately pay attention to the fact that the length of the array can be any. The array can consist of any numbers and the number being searched for can also be any number.

Suppose we have an array of numbers from 1 to 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
]

Linear search

Let’s start with the definition.

Linear search is a simple algorithm for finding an element in a data structure (such as an array) that sequentially checks each element in the data structure for a match with a target value. It starts with the first item and continues checking until the item it is looking for is found or until the entire data set is exhausted.

Let’s write a function that will check all elements of the array in turn:

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

If how targetNumber we will pass 1then we need one iteration of the loop to find the number.

If how targetNumber we will pass 100then we will need 100 iterations of the loop to find the number.

There is a difficulty in this algorithm O(n). Such complexity is called linear complexity.

Such a search is extremely inefficient when working with a large set of data.

Binary search

Binary search much more efficient compared to linear search.

Binary search is based on the idea of ​​dividing the data into halves and then searching in one of them with subsequent distribution.

The principle of binary search

Let’s say we’re looking for the number 87 in our sorted list of numbers from 1 to 100.

First action:

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
]
  • Let’s look at the last element of the array one. 49 more than 87? No.

  • Then we look at the last element of the array two. 100 more than 87? Yes, so searching for a number will be an array two. With the first action, we already cut off half of the data.

Second action:

  • Massif two divide again into two. We get an array three with numbers from 50 to 75 and four with numbers from 76 to 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
    ]
  • Let’s look at the last element of the array three. 75 more than 87? No.

  • Then we look at the last element of the array four. 100 more than 87? Yes, it means that the number will be searched in the array four. In the second action, we cut off another half of the data.

The third action:

  • Massif four divide again into two. We get an array five with numbers from 76 to 87 and an array six with numbers from 88 to 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
    ]
  • Let’s look at the last element of the array five.

  • Is 87 greater than 87? No. They are equal. We found our number on the third act.

Binary search algorithm

Binary search only works if the list is sorted!

By assignment condition, we can have any array length and any sorted numbers at the beginning of the array.

Let’s write a solution for our task using binary search.

To begin with, we need to generate the following arrays.

Let’s write a function getRandomNumberwhich returns a random number in the given range:

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

  // Максимум не включается, минимум включается
  return Math.floor(Math.random() * (max - min) + min);
}

Let’s write a function createRandomNumberArraywhich returns an array of numbers of the given length with the numbers sorted.

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

Next, we will write the function binarySearchwhich will return an object with the found index (or -1) and with the number of loop iterations we’ve gone through.

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 }
}

We will also write a function linearSearch c by a normal linear search, which will return the object with the found index or -1 and with the number of iterations of the loop we went through.

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 }; // Элемент не найден
}

We will get the following data:

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

And finally, let’s create the array itself:

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

And at the end, we will run our code and compare the number of loop iterations in functions and functions:

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)

Full version of the code:

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)

Let’s see the console with the execution results:

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 }

In these five cases:

  • The binary search required 7 to 10 loop iterations.

  • The linear search required 19 to 496 loop iterations.

For linear search, the maximum number of iterations coincides with the size of the array.

The case is different with binary search. If the list consists of 100 items, more than 7 attempts are required. A list of 4 billion elements requires at most 32 tries. Impressive, right?

Binary search is performed in logarithmic time and has complexity O(log n).

Logarithms

Logarithm is a mathematical function that tells us how many times a certain number (called the base of the logarithm) must be multiplied by itself to get another number.

Let’s imagine that we have the number 1000. If we take the logarithm of the number 1000 to the base 10, the result is 3. This means that 10 times itself three times (10 * 10 * 10) is 1000.

Logarithm is the inverse operation of exponentiation.

In our case log always means log to the base 2.

Binary search requires no more in the worst case log n checks

A list of 8 log 8 elements requires more than 3 checks because 2^3 = 8.

For a list of 1024 elements, log 1024 is at most 10 checks, because 2^10 = 1024.

Related posts