Binary search can be said to be all the algorithm of the most basic, one of the easiest to understand the algorithm, but in fact is one of the highest rate of failure, in each big factory of fresh students interview, such evaluation is common: talk about the project to talk well, call him to write a binary search but can not write out. I do not comment on this, in terms of binary search, I think it is not as easy as we imagine, with “the idea is very simple, details are the devil” to describe the most appropriate, do not believe that we take a look step by step.

Difficulty 1: boundary judgment

Binary lookup code is roughly as follows:

let binarySearch = (arr, target) = > {
    let begin = 0;
    letend = ??? ;while(??????? { int mid = begin + (end -begin) /2;
        if(arr[mid] == target) {}
        else if(arr[mid] > target) {}
        else if(arr[mid] < target) {}
    }
    return????? ; }Copy the code

As can be seen, the problem has become obvious. Many people can write the basic framework without preparation, but the boundary conditions have been unclear, resulting in emotional tension, confusion of thinking, and finally nothing.

Now let’s just break down the various boundary conditions,

let search = (arr, target) = > {
    let begin = 0;
    let end = arr.length- 1; // The search interval is [begin, end], which is a closed interval
    while(begin <= end) {// Start = end; // Start = end;
                         // Stop only when begin>end
        let mid = (begin + end) >>> 1;// Bit operation, unsigned right shift one, same as math.floor ((begin+end)/2)
        if(arr[mid] == target) {
            return mid;
        }
        else if(arr[mid] > target) {
            end = mid - 1;[left, mid-1]
        }
        else if(arr[mid] < target) {
            begin = mid + 1; // The search range becomes [mid + 1, end]}}return - 1;
}
Copy the code

In fact, we can also do this:

let search = (arr, target) = > {
    let begin = 0;
    let end = arr.length; // This is equivalent to the search interval [begin, end], which is a closed before open interval
    while(begin < end) {/ / key points:
                       // When begin equals end, there are no values in the interval
        let mid = (begin + end) >>> 1;
        if(arr[mid] == target) {
            return mid;
        }
        else if(arr[mid] > target) {
            end = mid;[left, mid-1]
        }
        else if(arr[mid] < target) {
            begin = mid + 1; // The search range becomes [mid + 1, end]}}return - 1;
}
Copy the code

I think the comments are clear enough, so I hope you can understand the principles of interval determination rather than just memorizing the code.

By the way, we can also write it recursively based on the above ideas:

let search = (nums, target) = > {
    let helpSearch = (nums, begin, end, target) = > {
      if(begin > end) return - 1;
      let mid = (begin + end) >>> 1;
      if(nums[mid] == target) return mid;
      else if(nums[mid] > target) 
        return helpSearch(nums, begin, mid - 1, target);
      else 
        return helpSearch(nums, mid+1, end, target);
    }
    // Closed interval form
    return helpSearch(nums, 0,  nums.length - 1, target);
}
Copy the code
let search = (nums, target) = > {
    let helpSearch = (nums, begin, end, target) = > {
      if(begin >= end) return - 1;
      let mid = (begin + end) >>> 1;
      if(nums[mid] == target) return mid;
      else if(nums[mid] > target) 
        return helpSearch(nums, begin, mid, target);
      else 
        return helpSearch(nums, mid+1, end, target);
    }
    // open interval form
    return helpSearch(nums, 0,  nums.length, target);
}
Copy the code

Difficulty 2: repeated target values

Let’s get straight to the real question:

Order log n level of time complexity, which is essentially binary search, which means we need to find the leftmost and the rightmost of the target value using binary search, which is a little bit more complicated.

Let’s disassemble it step by step.

Look for the left boundary

let left = 0;
let mid;
let right = nums.length;
while(left < right) {
  mid = (left + right) >>> 1;
  if (nums[mid] > target) {
      right = mid;
  } else if (nums[mid] < target) {
      left = mid + 1;
  } else if (nums[mid] == target) {
      right = mid; / / the key}}Nums [left] must be greater than or equal to target
if (left == nums.length) return - 1;
else return nums[left] == target ? left : - 1;
Copy the code

Look for the right boundary position

let left = 0; 
let right = nums.length;
while(left < right) {
  mid = (left + right) >>> 1;
  if (nums[mid] > target) {
      right = mid;
  } else if (nums[mid] < target) {
      left = mid + 1;
  } else if (nums[mid] == target) {
      left = mid + 1; / / note}}[left] = nums[left] = nums[left]
if (left == 0) return - 1;
else return nums[left - 1] == target ? left - 1: - 1;
Copy the code

Of course, I’m using front closed and back open intervals here, but you can just do it with closed intervals.

Final code presentation

var searchRange = function(nums, target) {
  let left = 0;
  let mid;
  let right = nums.length;
  while(left < right) {
      mid = (left + right) >>> 1;
      if (nums[mid] > target) {
          right = mid;
      } else if (nums[mid] < target) {
          left = mid + 1;
      } else if(nums[mid] == target) { right = mid; }}let leftIndex = - 1, rightIndex = - 1;
  if (left == nums.length) return [- 1.- 1];
  else leftIndex = nums[left] == target ? left : - 1;

  left = 0; right = nums.length;
  while(left < right) {
      mid = (left + right) >>> 1;
      if (nums[mid] > target) {
          right = mid;
      } else if (nums[mid] < target) {
          left = mid + 1;
      } else if (nums[mid] == target) {
          left = mid + 1; }}if (left == 0) return [- 1.- 1];
  else rightIndex = nums[left - 1] == target ? left - 1: - 1;
  
  return [leftIndex, rightIndex];
};
Copy the code

All in all, dichotomous search thinking is not difficult, but to understand the interval meaning of the boundary variable is very clear, so as not to think disorder, details are considered clearly, various methods can come and go freely.