“This is the 26th day of my participation in the First Challenge 2022. For details: First Challenge 2022.”

Hi, everybody. I’m handsome.

Today is about dichotomy search ah, smelly treasure may feel dichotomy search light look at “dichotomy” two words have learned the principle.

Indeed, the principle of binary search is very simple, but often the simpler the more difficult to master, do not draw simple and easy equal sign.

Especially when dichotomy search solves the actual problem, should be extremely cautious, do not pay attention to a little in detail, smelly treasure people can give oneself a “bug manufacturing machine” title.

As for whether it is really so wicked, read on to find out.

Understanding binary search

Binary Search, also known as the Binary Search.

Binary lookup requires that the number of * to be searched must be in an ordered array *. Under this premise, take the number of middle positions as the comparison object:

  • If the value you are looking for is equal to the intermediate number, the search succeeds.
  • If it is less than the middle number, the search continues in the left half of the middle position.
  • If it is greater than the middle number, the search continues in the right half of the middle position.

The above process is repeated until the search succeeds or the search area becomes 0 and the search fails.

Binary search is everywhere in our life, such as writing a positive integer within 100, and the punks guess which one I write, I only answer is big or small.

The practice of a fool is to guess one by one, this will not say. Binary search would look like this (partially) :

Since it’s a positive integer up to 100, I guess 50 on the first try, 25 on the second try, 75 on the second try, and so on.

Assuming the number to guess is 1, the process is as follows:

digital The first The 2nd The third time 4 times The fifth time 6 times The seventh
1 50 25 12 6 3 2 1

You see, it only took me seven times to find it, so that’s pretty fast, and that’s in the worst case, which is a binary search of 100 numbers and you get the answer in at most seven times.

According to the idea of binary search, the binary search of 1000 numbers only need to search 10 times at most, the number of less than 10000 only need to search 14 times at most, who does not believe that you can start to try, if you are not afraid of tired words.

Below I take stinky treasure hand – in – hand reproduction of a binary search.

Look for the value 21 in the array 10, 11,21,32,53,85,138,223,361.

Using the dichotomy idea, set low and high to represent the left and right subscripts of the interval to be searched, and mid to represent the middle element subscripts of the interval to be searched.

The process is shown in the figure below:

Through the above explanation and examples, I believe that your knowledge of binary search is enough. Here is how to implement binary search.

Binary search general implementation

With the idea of binary lookup, let’s look at a general implementation of binary lookup.

def BinarySearch(arr, low, high, target): low, high = 0, len(arr) - 1 while low <= high: Mid = (low + high) / 2 if arr[mid] == target: return mid if arr[mid] < target: low = 1 else: high = mid - 1Copy the code

This is one of the most basic binary search code, does it look very simple?

A lot of stinky treasure feel that after looking at the idea of binary search, binary search code will come out directly.

Experience tells us that the more simple something is, the more likely it is to stumble in detail. If you are going to pick up the keyboard now and disagree, THEN I suggest you take a piece of paper and write one by hand.

Let me know in the comments section if you’re doing anything right. I want to be your lick dog.

That was a little bit of an interlude, but now I’m going to get back to the point, and I’m going to elaborate on what I need to pay attention to.

Pit 1: while loop exit condition

The condition for the while loop is low <= high, not low < high.

Why is that? Let me elaborate.

First of all, it is important to clarify that the current binary search is looking for the [low, high] interval, which is the left closed interval and the right closed interval.

We stop every time we find the target value in the search interval:

if arr[mid] == target:
        return mid
Copy the code

Or the search interval becomes 0, the while loop terminates, and the search fails.

If the condition of the while loop is low <= high, then the condition of the loop terminates as low = high+1, and the interval is [high+1, high]. There must be no number greater than a large number and less than a small number, then the interval is 0. The while loop terminates.

If the condition of the while loop is low < high, the termination condition of the loop is equivalent to low = high, i.e., the interval is [high, high].

For example, high = 5, the interval is [5, 5], and there is a number 5, so it is not empty.

The interval [5, 5] is forcibly discarded. If the target is the same number with index 5, it will be discarded.

Pit 2: Low and high

My code values low and high like this:

low = mid + 1
high = mid - 1
Copy the code

Low = mid, high = mid

[mid] : [mid+1, right] : [mid+1, right] : [mid+1, right] : [mid+1, right] Because we already matched the element with the subscript mid, we don’t need to match it again.

Pit 3: mid

If the value of mid is set, there will be no problem.

mid = (low + high) / 2
Copy the code

But suddenly, I take Python, where an integer value is not limited by the number of digits, which normally means it can be infinitely large, but the computer has memory, so you have to have a limit.

The addition is always difficult to control. What if it gets really big?

So it is still comfortable to subtract, so when low or high is very large, mid can be set as follows:

mid = low + (high - low) / 2
Copy the code

So that’s pretty much the normal implementation of binary lookup.

This code, must repeatedly see repeatedly remember, had better be able to recite.

While it is important to understand the nature of data structures and algorithms themselves, it is also essential to “memorize code”, and few people put much effort into it.

Maybe a lot of people think that “memorizing code” is ridiculous, take “understanding can write out” for example, I feel that it is better to talk on paper.

When I was engaged in ACM, I always practiced intensively for each type of problems and had my own summary template for each type. I practiced a lot and memorized the code to form muscle memory, so that I could write it out quickly when I needed to write.

Think about how much of an advantage that would be if it were an interview.

Binary search time complexity

So let me do the result first, binary search is order logn.

How did this come out? Very good.

An array of length n would assume that every time a binary search is done, the range to be searched will be half of the original range, and in the worst case, it will not stop until the search space is zero.

So its search interval will be n the first time, n/2 the second time, and (n/2)/2 the third time. Assuming x cycles, the formula becomes:

That is:

So:

As I said in my book, logarithmic complexity, whether you base two, three, or ten, is called O(logn).

As for why, forget, can review again.

Binary search, that’s pretty much the end of it.

In summary, binary search is a matter of essence, detail control, in use of two must play twelve points of spirit.

Understand the above content, the basic dichotomy will not be too big a problem.

Of course, for dichotomy is not limited to this, or many deformation problems. This article mainly writes the general operation in the ideal situation, the actual situation will not say that your array is monotonous, of course, as a beginner, now enough content.

Anyone who can bear to see this is true love. Give it a thumbs up.

I’m Handsome. I’ll see you next time.