Here for you to sort out the core idea of binary search algorithm, more is to give some questions for readers to think about, so do not spend a large section of the details of binary search algorithm. I believe that after the reader’s continuous practice and thinking, summary, understand the idea of binary search algorithm, and then deal with the problem of binary search can be easily solved.

The main content is from the “force button” 287 (find the number of repeats) answer the comments of the netizens.

The core idea of binary search

The core idea of binary search is “reduce and cure”, that is, “reduce the problem scale continuously”.

Two ideas of binary search

  • Idea 1:while(left <= right)This looks for elements directly inside the loop body and exits the loopleft 和 rightNot coincident, interval[left, right]Is an empty interval;
  • Idea 2:while(left < right)It’s always eliminating elements inside the body of the loop; When you exit the loopleft 和 rightOverlap, interval[left, right]Shrink into
    1 1     An element.

The following two animations show the execution of these two ideas.

The second way of thinking can be summed up as “move the left and right boundaries to the middle, then cut both sides, and the last number left may be the target element”. This way of thinking can simplify the process of thinking when solving complex problems.

We won’t show you how to write the code here. My advice is to think about how to write code based on the two ideas mentioned above. When faced with a problem, choose one of the two ideas and implement it. You don’t need to write it out in both ways.

The details of the code, there are some pits and matters needing attention, whether I write the problem solution, or the introduction of other friends, there is no lack of such content, compared with the introduction of others, the key is to practice, thinking, in order to deeply understand the idea of binary search algorithm design.

Three kinds of question types of binary search

  • To find a number in an array, called binary subscript;
  • Finding an integer in a range of integers is called “binary answer”;
  • Through the correlation between one variable and another variable, and then determine the value of the target variable, collectively referred to as “complex problem”.

For detailed introduction and examples of this part, please refer to question 35 of “Force Button”.

Why do I never get binary search right?

I think: binary search is not difficult, just in the inspection whether we are careful, if encountered in the interview, is certain to win. Do not understand the boundary conditions, not very serious, may be in the back of the template, did not understand the idea and inside very detailed places.

  • My experience is to define the interval as: left-closed and right-closed interval, and the left and right boundaries should be the same. Making it left-closed and right-open will increase the complexity of problem solving.
  • clearint = left + (right - left) / 2Here, divided by
    2 2     Is the bottom round (think about the top round, when do you need the top round, why do you divide by
    2 2     , or other integers);
  • clearwhile(left <= right) 和 while(left < right)There are essential differences in the way of thinking between these two writing methods. How to write the logic inside should be well known.
  • Always think about what the next search interval will be, which is the point above: “Always think of the interval as beingLeft closed right closedInterval “, which will help us figure out whether the boundary can be reached, equal to,
    + 1 + 1     、
    – 1 – 1     And so on, because even though it’s defined as a closed left open right interval[left, right)It must correspond to an equivalent left-closed and right-closed interval[left, right - 1];
  • Thinking clearly about the semantics behind each line of code to ensure semantic clarity is also a very effective way to write correct code and reduce bugs;
  • An important way to understand the idea of an algorithm is to debug, which is not a very sophisticated technique, but to print out the values of variables and look at them in the belief that you can solve the problem of why the code you write creates an endless loop and come up with a solution.

In the following video, I’m going to be very specific about how I analyze and do binary search.

Note: Wechat can not show the link, you can see my explanation video in the problem solving area of the website “Likou”, the location is relatively conspicuous, easy to find.

  • 35.
  • 1095: Official solution;
  • Problem 4: Official solution.

The detailed details of dichotomy search, can check me in “force buckle” the solution of the 35th problem: “write dichotomy search problem, a few kinds of template writing method with the introduction and comparison”.

Here’s the thing: “template” is just a noun, and I’m going to focus on algorithmic ideas in my presentation, so the advice is to understand ideas, the two ideas I mentioned at the beginning (find elements directly in the loop body and exclude elements in the loop body).

That’s all for today and thank you for watching.