1 – binary search algorithm

① Binary lookup arrays are ordered

The binary search starts in the middle of the array. If found, the search ends and the subscript is returned. Otherwise, the midValue of the array is compared with the value to be found. If findValue > midValue, all the values to the right of midValue in the array are divided again, and the search starts from the middle, so as to recurse. Conversely, if findValue < midValue, all values to the left of midValue are divided into two parts for recursive search. If the recursion is not found, -1 is returned.

const arr = [1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.16.17.18.19.20]

// When a value is found, its index in the array is returned. If not, -1 is returned
function searchValue(arr = [], findValue, left = 0, right = arr.length - 1) {
    // left > right if findValue is not found, findValue does not exist in array
    if (left > right) {
        return -1
    }
    const mid = parseInt((left + right) / 2)
    if (findValue > arr[mid]) {
        // Find a value greater than the median, recurse to the right
        return searchValue(arr, findValue, mid + 1, right) // Note that return is required
    } else if (findValue < arr[mid]) {
        // We recurse to the left if the value we are looking for is less than the median
        return searchValue(arr, findValue, left, mid - 1) // Note that return is required
    } else {
        // The value to be found is equal to the intermediate value, which returns the subscript in the array
        return mid
    }
}

console.info(searchValue(arr, 10))  / / 9
Copy the code

2 – binary search algorithm time complexity

Binary search time is O(log2n)

  • Log base 2n is a mathematical logarithm, base 2 what’s the logarithm of n, which is 2 to what power is n
  • O(log2n) is the time complexity of the algorithm, using the idea of a dichotomy, such as folding a line in half until it reaches a point
  • Time complexity refers not to specific time, but to the growth of operands