Ultimate bug finding method - two points

Ultimate search bug Dafa - Two points

Hello everyone , I am a lucifer. Today, I'd like to share with you some common things in my daily work debug is ！

Binary code

When I find a difficult to understand and find bug When , my 「 The ultimate solution 」 It's binary code .

For example, delete the file first a Half of the code （ about ）, Then test whether the problem is still .

• If the problem is gone , Then we found the code that went wrong .
• If the problem persists , Then we continue to use the same method , Continue deleting files a Half of the code （ about ）, Then test whether the problem is still .
• Repeat the above steps , Until you find the wrong code

This method is very useful when I have no thoughts or help others locate problems . Due to this practice, the time complexity is roughly logn, Therefore, we can roughly locate the problem code in just a few times . Similarly , We can also perform bisection in multiple files at the same time .

Submit in two

More time , We found one between two releases bug. There are several between these two releases commit Of , also commit There's a lot more （ Dozens or even hundreds ）.

We can also use a similar method .

• First switch to the intermediate submission between two releases x（ Even if you have to submit x The distance difference between two releases is the smallest ）.

*

In fact, the minimum distance difference is either 0, Or 1

*

• Verify whether the problem exists . If it doesn't exist , We are not sure that this is the problem of submission , You might as well mark the current submission first c by good. If there is , You may wish to mark the current submission c by bad.

• Go through the mark on it , We can find the earliest presentation bad The submission of , And the most important thing is that the complexity is logn, among n For the total number of submissions we need to verify . obviously , This workload is more than checking one by one commit Much faster .

*

Don't understand the principle ？ We'll talk about it later .

*

Git Binary search in

git Developers of also thought of this , So it provides bisect Command to help us do the above things .

Use bisect Problem finding mainly depends on the following three commands ：

1. git bisect start

Start a search ,start You can add good and bad The submission point of ：

git bisect start [rev bad] [rev good]

If not good and bad The submission point of , that git Will wait until we use good and bad The command specifies the corresponding submission point and starts searching

2. git bisect good

It is correct to mark a submission point , You can add rev To specify a specific submission point , If not , Then the current submission point is marked by default .

3. git bisect bad

It is used to mark a submission point that contains problems , If bad You can add rev To specify a specific submission point , If not , Then the current submission point is marked by default .

The principle behind it

Let's fill the hole in front . Why go through such a mark , We can find the first problem （ Mark bad） Submission of ？ And the time complexity is .

There is just a principle of force buckle , Let's use it directly .

Title address (278. First wrong version )

https://leetcode-cn.com/problems/first-bad-version/

Title Description

 You are the product manager , Currently leading a team to develop new products . Unfortunately , The latest version of your product doesn't pass the quality test . Because each version is based on the previous version , So all versions after the wrong version are wrong .

 Suppose you have  n  A version  [1, 2, ..., n], You want to find out the first wrong version that caused all subsequent versions to go wrong .

 You can call  bool isBadVersion(version)  Interface to determine version number  version  If there is an error in unit test . Implement a function to find the first wrong version . You should try to minimize calls to  API  The number of times .

 

 Example  1：

 Input ：n = 5, bad = 4
 Output ：4
 explain ：
 call  isBadVersion(3) -> false
 call  isBadVersion(5) -> true
 call  isBadVersion(4) -> true
 therefore ,4  It's the first wrong version .


 Example  2：

 Input ：n = 1, bad = 1
 Output ：1


 

 Tips ：

1 <= bad <= n <= 231 - 1

Ideas

It can be seen that , This process is the same as that described above . And our goal is to find the first submission that goes wrong .

Just to be clear ：

• If a version x yes good Of , that [1, x] All submissions between must be good Of , Therefore, the version to be detected becomes [x+1,n]
• If a version x yes bad Of , that [x, n] All submissions between must be bad Of . Because we are looking for the first problematic version , Therefore, the version to be detected becomes [1,x-1]

So no matter what version we detect good still bad, We can all reduce the number of versions to be tested to half , That is to say, we can be in Find the first problematic version within times .

If you've seen my dichotomy , You should know this is what I summarized 「 The leftmost two 」.

• Two sub topics （ On ）
• Two sub topics （ Next ）

Code

• Language support ：Python3

Python3 Code:

class Solution:
    def firstBadVersion(self, n):
        l, r = 1, n
        while l <= r:
            mid = (l + r) // 2
            if isBadVersion(mid):
                #  shrinkage 
                r = mid - 1
            else:
                l = mid + 1
        return l

「 Complexity analysis 」

• Time complexity ：
• Spatial complexity ：

summary

Dichotomy is widely used in daily work , Dichotomy bug Is one of the most practical skills . The simplest two-point search bug You can delete the contents of the file . And if there are many files , It's not convenient , At this time, we can use binary submission to complete .

The principle is also very simple , It's a simple leftmost two . If you are not familiar with this , It is strongly recommended to look at the dichotomous topics mentioned in the article , A summary of 20000 words will definitely make you gain .