preface

Hi, I’m Lucifer. Today I bring you a special topic called “Dichotomy”. First of all, the outline of this paper is a brain map I drew with MindMap. Later, I will continue to improve and gradually improve other topics.

You can also use vscode blink-mind to open the source file and view some notes in it. The source files can be obtained by replying to the brain map on my public account “Likou Jiajia”, and the brain map will continue to update more content in the future. Vscode plug-in address: marketplace.visualstudio.com/items?itemN…

This series includes the following topics:

  • After almost finishing all the links, I found these things…
  • Almost finished brushing all the tree buttons, I found these things…
  • After almost finishing all the questions, I found these things… (on)
  • After almost finishing all the questions, I found these things… (below)

This topic is expected to be carried out in two parts. The first part focuses on basic concepts and a focus. With that in mind, in part two we’ll continue with the two dichotomous types and four applications.

The content of this article has been synchronized to my brush plug-in RoadMap, with brush plug-in taste better oh, access to plug-ins can be in my public account in likejiajia plug-in view.

If you find the article useful, please like it and leave a comment to forward it so that I will be motivated to continue doing it.

preface

In order to prepare this topic, I have not only finished all the Binary questions in the Binary Search, but also finished all the Binary questions in another OJ website, Binary Search. There are over 100 Binary questions in total. If you feel useful, you can tell me through the way of likes and forwarding, if you like more people, I will continue to publish the next article as soon as possible oh ~

Binary search is also known as half search algorithm. In a narrow sense, binary search is a search algorithm that looks for a particular element in an ordered array. And that’s the way most people know it. In effect, generalized binary search reduces the size of the problem by half. Similarly, the rule of thirds reduces the size of the problem by a third.

This article is about binary search in the narrow sense, but if you want to look at other kinds of binary search in the broad sense you can check out a post THAT I wrote earlier and look at dichotomy in terms of rat poisoning

While the basic idea of binary lookup is relatively simple, the details can be overwhelming… – gartner,

When Jon Bentley gave binary search problems to students in a professional programming class, 90 percent of the students were still unable to come up with the correct solution after hours, mainly because the bug programs didn’t work when confronted with boundary values or returned incorrect results. A study conducted in 1988 showed that only five out of 20 textbooks correctly implemented binary search. Not only that, bentley’s own 1986 book “Programming Abet” binary search algorithm has integer overflow problem, undetected for more than 20 years. The same overflow problem in binary search algorithms implemented by the Java language library was fixed for more than nine years.

Binary search is not easy, this article will try to take you close to TA, understand the underlying logic of TA, and provide templates to help you write the book Bug Free binary search code. After reading the handout, I suggest you practice binary search with LeetCode Book.

The basic concept

First we need to know some basic concepts. These concepts have a very important role in learning dichotomy, and then encountered these concepts will not be told, the default is that you have mastered.

Solution space

The solution space is the set of all possible solutions to a problem. For example, a problem could have all the solutions 1,2,3,4,5, but only one of them in any one case (it could be 1,2,3,4,5). So the solution space here is the set of 1,2,3,4,5, and it could be any of those values in any particular case, and our goal is to figure out which one it is in any particular case. If linearly enumerates all the possibilities, the time complexity for enumerating this part is O(n)O(n)O(n).

Examples are given:

If you are asked to look for target in an array nums, return the index if it exists, or -1 if it does not. So what’s the solution space for this problem?

It is obvious that the solution space is the interval [-1, n-1], where n is the length of NUMs.

Note that the solution space of the above problem can only be integers between [-1,n-1]. A decimal such as 1.2 is impossible. This is actually the case for most dichotomies. But there are also a few problems where the solution space includes decimals. If you have decimals in your solution space, you might have a precision problem, and you should be aware of that.

For example, if you were asked to take the square root of a number x, the answer would be correct within 10−610^-610−6. It is easy to know that the size of the solution space can be defined as [1,x] (more precisely, but we’ll talk about that later), and that the solution space should include all the real numbers in the interval, not just integers. At this time, the solution idea and code have not changed much, only two changes need to be:

  1. Update the step size of the answer. For example, the previous update wasl = mid + 1Now,mayIt doesn’t work. So here it ismayThe correct solution will be missed, for example, if the correct solution happens to be a decimal within the interval [mid,mid+1].
  2. You have to consider the error when you’re judging conditions. Because of precision problems, the end condition of the judgment may be within a certain range of the answer.

For search problems, the solution space must be limited, otherwise the problem is unsolvable. For search problems, the first step is to define the solution space so that you can search in the solution space. This technique applies not only to dichotomies, but to any search problem, such as DFS, BFS and backtracking. But for dichotomy, it is more important to specify the solution space. If you don’t understand this sentence by now, you probably will by the end of this article.

One of the rules when defining a solution space is that it can be large but not small. Because if the solution space is too large (as long as it is not infinitely large), it is just a few more operations, while if the solution space is too small, the correct solution may be missed, resulting in wrong results. For example, if we want to find the square root of x, we can define the solution space to be smaller, such as [1,x/2], so as to reduce the number of operations. But if you set it too low, you might miss the correct solution. This is one of the rookie mistakes.

Some students may say I can’t see how to do it. I think it’s okay if you’re really unsure, if you take the square root of x, you can even take [1,x], just let it do more operations. I suggest you set a wide range for the upper and lower bounds. You can get stuck a little bit more as you get to know the dichotomy.

The sequence order

I’m talking about sequences here, not arrays, linked lists, etc. That is to say, dichotomy usually requires sequential order, not necessarily arrays, linked lists, but other data structures. There are other things that are ordered and it’s easier to just say it out loud. Some are hidden in the title information. At first glance, the title does not have ordered keywords, but order is hidden in the lines. For example, they give an array nums, and they don’t limit nums to be ordered, but they limit NUMs to be non-negative. So if you prefix nums and or prefix or (bit operation or), you get an ordered sequence.

More tips can be found in the four application sections.

Although dichotomy does not imply sequential order, most dichotomous questions have the salient feature of order. Except:

  • Some of them directly define order. This kind of question is usually not difficult, but also easy to think of dichotomy.
  • Some require you to construct your own ordered sequence. These types of questions are usually difficult and require some ability to observe.

Like Triple Inversion. The title description is as follows:

Given a list of integers nums, return the number of pairs I < j such that nums[I] > nums[J] * 3. N ≤ 100,000 where n is the length of nums Example 1 Input: nums = [7, 1, 2] Output: 2 Explanation:  We have the pairs (7, 1) and (7, 2)Copy the code

This problem does not define the array nums to be ordered, but we can construct an ordered sequence D and then divide d. Code:

class Solution:
    def solve(self, A) :
        d = []
        ans = 0

        for a in A:
            i = bisect.bisect_right(d, a * 3)
            ans += len(d) - i
            bisect.insort(d, a)
        return ans
Copy the code

It doesn’t matter if you don’t understand the code right now, but just to give you an idea that there’s a type of problem, you can go back to this problem after you’ve read all of this chapter.

The extreme

Similar to the extreme values I mentioned in the heap topic. Except the extremes here are static, not dynamic. The extremum here usually refers to finding the KTH largest (or KTH smallest) number.

A very important use of a heap is to find the KTH largest number, and dichotomy can also find the KTH largest number, but the idea is completely different. The idea of using a heap to find the KTH largest is explained in detail in the topic on heaps mentioned earlier. How about two? Here we take an example: This question is Kth Pair Distance. The title description is as follows:

Given a list of integers nums and an integer k, return the k-th (0-indexed) smallest abs(x - y) for every pair of elements (x, y) in nums. Note that (x, y) and (y, x) are considered the same pair.

Constraints:n ≤ 100,000 where n is the length of nums
Example 1
Input:
nums = [1, 5, 3, 2]
k = 3
Output:
2
Explanation:

Here are all the pair distances:

abs(1 - 5) = 4
abs(1 - 3) = 2
abs(1 - 2) = 1
abs(5 - 3) = 2
abs(5 - 2) = 3
abs(3 - 2) = 1

Sorted in ascending order we have [1, 1, 2, 2, 3, 4].
Copy the code

Given an array nums, you are asked to find the absolute value of the difference between any two numbers of the KTH value of nums. Of course, we could use the heap to do this, but the time complexity of using the heap would be too high to pass all the test cases. We can use dichotomy to reduce dimension for this problem.

For this problem, the solution space is the difference between 0 and the maximum and minimum values in the array nums, expressed as [0, Max (nums) -min (nums)]. Once we know the space, we need to divide the solution space. For this problem, we can take the middle of our solution space, mid, and calculate the absolute value of the difference between any two numbers that are less than or equal to the middle. Let’s call this number x.

  • If x is greater than k, then any number greater than or equal to mid in the solution space cannot be the answer and can be discarded.
  • If x is less than k, then any number in the solution space less than or equal to mid cannot be the answer and can be discarded.
  • If x is equal to k, then mid is the answer.

Based on this, we can use dichotomy to solve. This type of question, I summarize as counting dichotomy. I’ll focus on the four applications later.

Code:


class Solution:
    def solve(self, A, k) :
        A.sort()
        def count_not_greater(diff) :
            i = ans = 0
            for j in range(1.len(A)):
                while A[j] - A[i] > diff:
                    i += 1
                ans += j - i
            return ans
        l, r = 0, A[-1] - A[0]

        while l <= r:
            mid = (l + r) // 2
            if count_not_greater(mid) > k:
                r = mid - 1
            else:
                l = mid + 1
        return l
Copy the code

It doesn’t matter if you don’t understand the code right now, but just to give you an idea that there’s a type of problem, you can go back to this problem after you’ve read all of this chapter.

A central

There is a central point of dichotomy that you must keep in mind. The rest (such as sequential order, left and right double Pointers) are the hands and feet of dichotomy, are appearances, not essence, while the half-fold is the soul of dichotomy.

I’ve given you a clear idea of what space is. And this cut in half is really just a cut in half of the solution space.

For example, the solution space is [1, n] (n is an integer greater than n). Somehow, we determine that the interval [1, m] cannot be the answer. Then the solution space becomes (m,n), and keep going until the solution space becomes trivial.

Note that the left side of the interval (m,n] is open, indicating that m cannot be taken.

Obviously the difficulty of half is to abandon which part according to what conditions. Here are two keywords:

  1. What condition
  2. What to leave out

Almost all the difficulty of dichotomies lies in these two points. If these two points are identified, almost all dichotomy problems can be easily solved. Fortunately, the answers to both of these questions are usually limited, and the questions tend to focus on those ones. So this is what we call a routine. I will introduce these routines in detail in the next four application sections.

Summary of the first chapter of dichotomy

The last part is mainly to introduce you to a few concepts, these concepts are very important for the problem, please be sure to grasp. And then we have the center of the dichotomy, the half, and this center requires you to do any dichotomy in your head.

If I had to sum up dichotomy in one sentence, I would say that dichotomy is an algorithm that makes the unknown world impossible to multiply. The dichotomy is that we can give up half of the solution anyway, so we can cut the solution space in half anyway. The difficulty is the two points mentioned above: what conditions and what parts to leave out. This is the problem at the heart of dichotomy.

That’s all the content of “Binary Topic (Part 1)”. If you find the article useful, please like it and leave a comment to forward it, so that I will be motivated to continue to the next episode.

Fixation of trailer

The last video was the basic concept. In the next video we’ll look at two types of dichotomy and four applications of dichotomy.

Next contents:

  • Two types of

    • The most left insert

    • The right insert

  • The four applications

    • Ability test dichotomy

    • Prefix and dichotomy

    • Insert sort dichotomy

    • The count of binary

Two of these types (leftmost and right-most inserts) mainly deal with how to use code to find specific solutions when the solution space is already defined.

The four applications mainly solve: how to construct solution space. It’s more about how to build ordered sequences.

These two parts are very practical content, while understanding these two parts, please be sure to keep in mind a central half. See you next time

The above is all the content of this article, you have any views on this, welcome to leave a message to me, I have time will check the answer one by one. I’m Lucifer, Github Over 40K STAR You can also pay attention to my public account “Li Kou Jia Jia” take you to bite the hard bone of the algorithm.