Gifs understand the implementation details of binary search

• Ordinary binary search

• Binary search on the left edge

• Dichotomous cable on the right boundary

• Binary search implementation details summary

• Shorthand CARDS

1 Ordinary binary search

let binatySearch = function(nums){
  let left = 0, right = nums.length - 1
  
  while (left <= right) {
    let mid = (left + right) >> 1
​
    if (nums[mid].value == target) {
      return mid
    }
    else if (nums[mid].value < target) {
      left = mid + 1
    }
    else { // nums[mid].value > target
      right = mid - 1}}return - 1 
}Copy the code

This public number before an article specifically introduced the cursor animation, how to understand the bubble algorithm of the boundary conditions?

Now the cursor animation has been updated to introduce a new animation element – line segment, let’s call this new animation line segment animation. Line segment animation has part of the characteristics of static visualization.

The interval represented by the left and right Pointers in the figure is [left, right].

From the line segment graph, we can understand the interval variation of left and right Pointers well.

We start with [left, right] representing the elements of the entire array, and then we keep reducing the range in half by the middle value. Because we have an ordered array, we shrink the right pointer if the middle value is greater than the element we’re looking for, and we shrink the left pointer if the middle value is less than the element we’re looking for.

If you understand the range variation, you will understand the code for mid + 1 and mid – 1.

Of course, the most important step in binary search is to take the left and right Pointers of the middle value is also a skill, details can be seen in my article: the clever use of bitwise operation – find the average of two integers

The examples in this article are written in the dumbest possible way to be easy to understand (lazy).

To make the animation easier to understand, elements selected as intermediate values in the diagram are highlighted in other colors.

Note that while (left <= right) why is <=?

While (left < right) = while (left < right)

let nums = [1.2.3.4.4.6.6.6.6.10.11.12.13.14.15.16.16.16.16]Copy the code

// [left, mid) mid [mid+1, right)
let binatySearchLeftBound = function(nums){
  let left = 0, right = nums.length
  while (left < right) {
    let mid = (left + right) >> 1
    if (nums[mid].value == target) {
      right = mid
    }
    else if (nums[mid].value < target) {
      left = mid + 1
    }
    else { // data[mid].value > target
      right = mid
    }
  }
  if(nums[left].value ! = target)return - 1
  return left
}Copy the code

// [left, mid-1] mid [mid+1, right]
let binatySearchLeftBoundClosed = function(nums){
  let left = 0, right = nums.length - 1
  while (left <= right) {
    let mid = (left + right) >> 1    
       
    if (nums[mid].value == target) {
      right = mid - 1
    }
    else if (nums[mid].value < target) {
      left = mid + 1
    }
    else { // data[mid].value > target
      right = mid - 1}}if(nums[left].value ! = target)return - 1
  return left
}Copy the code

// [left, mid) mid [mid+1, right)
binatySearchRightBound = function(nums){
  let left = 0, right = nums.length
  
  while (left < right) {
    let mid = (left + right) >> 1
    if (nums[mid].value == target) {
      left = mid + 1
    }
    else if (nums[mid].value < target) {
      left = mid + 1
    }
    else { // data[mid].value > target
      right = mid
    }
  }
​
  if (right <= 0 || nums[right- 1].value ! = target)return - 1
  return right- 1
}Copy the code

// [left, mid) mid [mid+1, right)
binatySearchRightBoundClosed = function(nums, node, timeline){
  let left = 0, right = nums.length - 1
  while (left <= right) {
    let mid = (left + right) >> 1
​
    if (nums[mid].value == target) {
      left = mid + 1
    }
    else if (nums[mid].value < target) {
      left = mid + 1
    }
    else { // data[mid].value > target
      right = mid - 1}}if (right < 0|| nums[right].value ! = target)return - 1
  return right
}Copy the code

Review past

Rule one:

If [left, right), then the condition of the while loop is while (left < right);

If [left, right], then the condition of the while loop is while (left <= right);