Binary Search is also called Binary Search, which is a highly efficient Search method. But the linear list has to be ordered.

First, the search process

  1. If the target value is equal to the intermediate element, the target value is found.
  2. If the target value is small, continue searching to the left.
  3. If the target value is large, continue searching on the right.
  4. Repeat the above steps until it is found, or the traversal is complete.

Two, a few common topics

1. Find a value in the array

Looks for a value in an ordered array, finds the return coordinate, can’t find return -1

function fn(arr, target) { let leftIndex = 0; let rightIndex = arr.length - 1; let middle; While (leftIndex <= rightIndex){middle = math.floor ((leftIndex + rightIndex) / 2); while (leftIndex + rightIndex){middle = math.floor ((leftIndex + rightIndex) / 2); If (target === arr[middle]){return middle} If (target < arr[middle]){rightIndex = middle + 1}else{leftIndex = middle + 1}} return -1} console.log(fn([8, 11], 9))Copy the code

2. Find the first value that matches the requirement

Retrieves a value from an ordered array. If there are more than one, return the leftmost coordinate. [8,8,9] return 1; [8,8,9] return 1;

function fn(arr, target) { let leftIndex = 0; let rightIndex = arr.length - 1; let middle; While (leftIndex <= rightIndex){// Ceil = floor Middle = math.floor ((leftIndex + rightIndex) / 2); middle = math.floor ((leftIndex + rightIndex) / 2); // // if(leftIndex === rightIndex){return arr[middle] === target? middle: If (target > arr[middle]){leftIndex = middle + 1}else{// target = middle, RightIndex = middle}} return leftIndex} console.log(fn([8, 8, 8, 8, 11], 8)Copy the code

There are a few points to note here:

  1. Some value of the judgment isBefore and after the position is consideredAnd then we have to continue processing, because it’s equal to timemiddleEither as the starting point or the end point of the next judgment, when there is only one value left, the same value left, middle and right, the judgment will beInfinite loop, we need to add oneleftIndex===rightIndex
  2. The median takeMath.ceilorMath.floorLook to the westmiddleTo whom it’s directly assigned. Assigned toleftIndexWhen usingMath.ceil. Assigned torightIndexWhen usingMath.floor. The reason is simple: make sureDirect assignmentThe two values of will not be equal.
  3. It must beGreater than the median value to the right, small equal to the left pack in the middle. Because it isLook for the first one on the leftIf the median is the value you’re looking for, then you don’t need to go back because it’s definitely not farther to the left. On the other hand, if you look for the right hand side, you might miss the first one in the middle. If it isLast positionthenThe equal sign should be greater than

3. Find or insert a number in the array

Given an ordered array arr and the target value target, return the coordinates if target is present in the array. If not, insert target into the array in array order and return the insertion position.

function fn(arr, target) {
    let leftIndex = 0;
    let rightIndex = arr.length - 1;
    let middle;
    while (leftIndex <= rightIndex){
        middle = Math.floor((leftIndex + rightIndex) / 2);
        if(target === arr[middle]){
            return middle
        }
        if(target > arr[middle]){
            leftIndex = middle + 1
        }else{
            rightIndex = middle - 1
        }
    }
    arr.splice(leftIndex, 0, target);
    console.log(arr)
    return leftIndex
}
console.log(fn([8], 7))
Copy the code
  1. This just needs to be returned based on the above, when it is judged to have a value.
  2. If it’s greater than the median, it’s less than the median.
  3. The last lvalue is where you want to insert it, right hereMath.floororMath.ceilWill do.

Third, summary

  1. Ordered array, find the location can be binary search.
  2. The loop needs to contain an array equal to (there is an array of length 1) without doing additional array length checks.
  3. If there isleftIndex=middleYou need to be careful about this direct assignmentMath.ceilandMath.floorThe choice of, don’t let the equality exist on both sides.