• This article was first published on:Algorithmic Customs Clearance Manual
  • Text code address (welcomePainted “Star” 和 “Fork”) :Github.com/itcharge/Le…

1. Algorithm introduction

Binary Search Algorithm, also known as “Binary Search Algorithm”, “logarithmic Search Algorithm”. Is a search algorithm that looks for a particular element in an ordered array.

Basic algorithm idea: first determine the range of the element to be searched, and gradually reduce the range until the element is found or cannot be found.

The process of binary search algorithm is as follows:

  • Each search starts with the middle element of the array. If the middle element is exactly the element to be searched, the search process ends.
  • If a particular element is greater than or less than the middle element, it looks in the half of the array that is greater than or less than the middle element, and compares from the middle element as it began.
  • If the array is empty at any step, it cannot be found.

For example, given an ordered array [0, 1, 2, 3, 4, 5, 6, 7, 8]. If we want to find out if 5 is in this array.

  • The first interval is the entire array[0, 1, 2, 3, 4, 5, 6, 7, 8]The median is zero4Because the4Less than5, so if5Exists in this array, so5Must be in4In the right half of the interval. So our search area becomes[4, 5, 6, 7, 8].
  • The second interval is zero[4, 5, 6, 7, 8]The median is zero6Because the5Less than6, so if5Exists in this array, so5Must be in6In the left half of the interval. So our search area becomes[4, 5, 6].
  • The third interval is zero[4, 5, 6]The median is zero5, is exactly the number we need to look for.

So we found that for an ordered array of length 9, it only took us three lookups to find the number we were looking for. If we were to iterate through the array, at worst, we’d have to look it up nine times.

A schematic diagram of the entire search process is shown below:

2. Algorithm idea

Binary search algorithm is the classical idea of “subtract and conquer”.

Here, “reduce” means to reduce the scale of the problem, and “cure” means to solve it. The combination of “subtract” and “cure” means “solve a problem by elimination.” That is, for each search, the interval in which there is no target element is excluded, and the search continues in the remaining interval in which there may be target elements. Each time through some conditional judgment, the search area is gradually reduced to achieve the purpose of “reducing the scale of the problem”. However, the scale of the problem is limited. After a limited number of searches, the target element will eventually be found or the search will fail.

3. Simple binary search

Below through a simple example to explain the next binary search ideas and code.

  • Title link: 704. binary search

3.1 Main Idea

Given an ascending array nums and a target value target, return target’s position in the array, or -1 if it cannot be found.

3.2 Solving the problem

Binary search algorithm is used to solve the problem.

Set the left and right nodes as both ends of the array, that is, left = 0, right = len(nums) -1, indicating that the interval to be searched is [left, right] (close left and close right).

Take the central location mid of two nodes, and compare the central location nums[mid] with the target value.

  • If the center position isnums[mid]With the targettargetIf it is equal, the central position is returned.
  • If the center position isnums[mid]Less than the target valuetarget, set the left node tomid + 1And then we’re going to continue to the right[mid + 1, right]Search.
  • If the center position isnums[mid]Greater than the target valuetarget, set the right node tomid - 1And then continue on the left[left, mid - 1]Search.

2.3 Problem solving code

class Solution:
    def search(self, nums: List[int], target: int) - >int:
        left = 0
        right = len(nums) - 1
        Select target from [left, right]
        while left <= right:
            Select the intermediate node of the interval
            mid = (left + right) // 2
            If the target value is found, return directly to the center location
            if nums[mid] == target:
                return mid
            If nums[mid] is less than the target value, the search continues in [mid + 1, right]
            elif nums[mid] < target:
                left = mid + 1
            If nums[mid] is greater than the target value, continue the search in [left, mid-1]
            else:
                right = mid - 1
        No element found, return -1
        return -1
Copy the code

4. Binary search for details

From the above example we understand the idea of binary search and specific code. But there’s a lot of detail you need to take into account when you’re actually solving binary search problems. For example, the following questions:

  1. Question of opening and closing interval: should the interval be left closed and right closed, or left closed and right open?
  2. midValue problem of:mid = (left + right) // 2, ormid = (left + right + 1) // 2?
  3. Judgment of exit conditions:left <= right, orleft < right?
  4. Search range selection:left = mid + 1,right = mid - 1,left = mid ,right = midHow should I write it?

Here are the explanations.

4.1 The opening and closing of the interval

The left closed right closed and left closed right open of the interval refer to the range of the initial interval to be searched.

  • Close left and close right: When initializing assignment,left = 0.right = len(nums) - 1.leftIs the position of the first element in the array,rightIs the position of the last element of the array, thus the interval[left, right]I can take any point on the left and right boundary.
  • Close left, open right: when initializing assignment,left = 0.right = len(nums).leftIs the position of the first element in the array,rightIs the next position of the last element of the array, thus the interval[left, right)The left boundary is accessible, but the right boundary is inaccessible.

On the left closed right closed, left closed right open, in fact, there are corresponding code solutions on the Internet. However, relatively speaking, in the process of solving the problem, the writing method of left closed and right open needs to be considered more complex, so it is recommended to use all “left closed and right closed” interval.

4.2 midThe value problem of

In practical binary search problems, the most common mid is mid = (left + right) // 2 or mid = left + (right-left) // 2. The former is the most common, and the latter is to prevent integer overflow. In this formula, // 2 represents the meaning of the middle number “round down”. When there is an even number of elements in the interval to be searched, the number in the middle is 2. In this case, only the number on the left of the middle can be obtained by using the above formula, but not the number on the right of the middle. So, is the number on the right actually operable?

Mid = (left + right + 1) // 2 mid = (left + right + 1) // 2 So if we’re looking for an even number of elements, we can get to the right of the middle number, and we can substitute this into 704. Binary search to try, found also can pass the subject evaluation.

This is because the idea of binary search is to determine which interval to search for the next element based on the value in the middle position of each selection. Each time, the selected element can be in the middle, but it does not have to be in the middle of the interval. It is ok to be a little to the left, a little to the right, or even a third or a fifth of the interval. For example, mid = left + (right-left + 1) * 1 // 5

But in general, elements in the middle work best in an average sense. And this is the easiest way to write it. In terms of whether the mid value is rounded down or up, most of the time, you choose not to increment 1. But in some ways, you have to think about adding 1, and we’ll talk about that later.

4.3 Judgment of exit conditions

We often see that in binary search algorithm writing, while statement out of bounds judgment statements are left <= right and left < right. So what exactly should we write in what context?

  • If the judgment statement isleft <= rightAnd the element to be searched does not existwhileDetermine that the statement is out of boundsleft == right + 1And I’ll write it in interval form[right + 1, right]At this time, the interval to be searched is empty, and no element exists in the interval to be searched, so the loop can be directly returned after termination- 1That’s right.
    • Let’s say interval(3, 2)There cannot be an element that is both greater than and equal to3Less than or equal to2, the loop is terminated and returns- 1Can.
  • If the judgment statement isleft < rightAnd the element to be searched does not existwhileDetermine that the statement is out of boundsleft == rightAnd I’ll write it in interval form[right, right]. At this point, the interval is not empty, there is still an element in the interval to be searched, and it is not certain that the element to be searched is not in this interval. At this point, the loop is terminated and returns- 1Is wrong.
    • Let’s say interval(2, 2)Elements,2It’s in this interval, and it terminates the loop and returns- 1I’m missing this element.

But what if we still want to use left < right?

You can add a layer of judgment to the return to determine whether the position pointed to by left is equal to the target element, and return left if it is, or -1 if it is not. That is:

#...
    while left < right:
        #...
    return left if nums[left] == target else -1
Copy the code

In addition, if left < right is used, it has the advantage of exiting the loop with left == right, so you don’t have to decide whether to return left or right.

4.4 Selection of search range

When selecting the range, sometimes it is left = mid + 1, right = mid-1, sometimes it is left = mid + 1, right = mid, sometimes it is left = mid, right = mid-1. So how do we determine the search range?

This is one of the difficulties of binary search, it’s easy to create an endless loop if you write wrong, or you don’t get the right result.

This is actually related to two different ideas of binary search algorithm.

  • Idea 1: “Find directly” — returns the result directly after finding the element in the loop body.
  • Idea 2: “Elimination” — There must be no interval in the loop body to exclude the target element.

So let’s talk about these two ideas.

5. Binary search for two ideas

5.1 Idea 1: Direct Search

The first approach is simpler, as soon as we find the element in the body of the loop, we return the result. In fact, we have used it above in “3. Simple binary search – 704. binary search”. Here’s another look at the idea and code:

Ideas:

  • Set mid to nums[mid].

    • If the center position isnums[mid]With the targettargetEqual,Direct returnThe index of the central location element.
    • If the center position isnums[mid]Less than the target valuetarget, set the left node tomid + 1And then we’re going to continue to the right[mid + 1, right]Search.
    • If the center position isnums[mid]Greater than the target valuetarget, set the right node tomid - 1And then continue on the left[left, mid - 1]Search.

Code:

class Solution:
    def search(self, nums: List[int], target: int) - >int:
        left = 0
        right = len(nums) - 1
        Select target from [left, right]
        while left <= right:
            Select the intermediate node of the interval
            mid = left + (right - left) // 2
            If the target value is found, go directly to the center of the range
            if nums[mid] == target:
                return mid
            If nums[mid] is less than the target value, the search continues in [mid + 1, right]
            elif nums[mid] < target:
                left = mid + 1
            If nums[mid] is greater than the target value, continue the search in [left, mid-1]
            else:
                right = mid - 1
        No element found, return -1
        return -1
Copy the code

Details:

  • The idea is to return the element as soon as it is found in the body of the loop.
  • The cycle can continue ifleft <= right.
  • If you exit the loop, there must be no target element in the interval.

5.2 Idea 2: Elimination

The second way to think about it is to exclude the target element from the loop body.

Ideas:

  • Take two node centersmidAccording to the judgment conditions, first exclude the interval where the target element does not exist.
  • Then continue to look for elements in the remaining interval and continue to exclude non-existent intervals based on conditions.
  • Until there is only one element left in the range, then determine if that element is the target element.

Following the second elimination idea, we can write two kinds of code.

The first code:

class Solution:
    def search(self, nums: List[int], target: int) - >int:
        left = 0
        right = len(nums) - 1
        Select target from [left, right]
        while left < right:
            Select the intermediate node of the interval
            mid = left + (right - left) // 2
            # nums[mid] = nums[mid] = nums[mid] = nums[mid] = nums[mid] = nums[mid
            if nums[mid] < target:
                left = mid + 1 
            # nums[mid] is greater than or equal to the target value. The target element may be in [left, mid], and the search continues in [left, mid]
            else:
                right = mid
        # check whether the remaining elements of the interval are target elements, otherwise return -1
        return left if nums[left] == target else -1
Copy the code

The second code:

class Solution:
    def search(self, nums: List[int], target: int) - >int:
        left = 0
        right = len(nums) - 1
        Select target from [left, right]
        while left < right:
            Select the intermediate node of the interval
            mid = left + (right - left + 1) / /2
            # nums[mid] = nums[mid] = nums[mid] = nums[mid
            if nums[mid] > target:
                right = mid - 1 
            # nums[mid] is less than or equal to the target value. The target element may be in [mid, right], and the search continues in [mid, right]
            else:
                left = mid
        # check whether the remaining elements of the interval are target elements, otherwise return -1
        return left if nums[left] == target else -1
Copy the code

Details:

  • The judgment statement isleft < right. So when you exit the loop, there must beleft == rightIf it’s true, you don’t have to say you should returnleftorright. It is also convenient to locate and find the subscript of the element. But be sure to make a final judgment on the remaining elements of the interval.
  • In the body of the loop, priority is givennums[mid]Under what circumstances must not be the target element, rule out the impossible interval, and then determine the range of the next search interval from the remaining interval.
  • In consideringnums[mid]At what point must not the target element be followed by its opposite (i.eelseIn general, there is no need to consider the range of the interval, directly take the inverse interval of an interval. If the last interval is zero[mid + 1, right]So the opposite is going to be[left, mid]. If the last interval is zero[left, mid - 1]So the opposite is going to be[mid, right].
  • The distinction is divided into two parts:[left, mid - 1] 与 [mid, right]When,midI’m going to round up. namelymid = left + (right - left + 1) // 2. Because if there are only two elements left in the intervalright = left + 1), once enteredleft = midBranch, the interval doesn’t get any smaller, and the next time around the interval is still the same[left, right]“, fell into an endless cycle.
  • The boundary setting can be remembered as: as long as you seeleft = midI’m going to round up. Or write it as:
    • left = mid + 1 和 right = mid 和 mid = left + (right - left) // 2It’s got to be a pair.
    • right = mid - 1 和 left = mid 和 mid = left + (right - left + 1) // 2It’s got to be a pair.

5.3 Applicable scope of the two ideas

  • Binary search idea 1: because the judgment statement isleft <= rightSometimes you have to think about returning isleftorright. There are three branches in the loop, and there must be one for exiting the loop or returning directly. This is a good way to solve simple problems. That is, the elements to be found are simple, the array is all non-repeating elements, and= =,>,<The situation is very easy to write about.
  • The idea of binary search 2: more in line with binary search algorithm subtraction thought. Each time exclude the target element must not exist in the interval, to achieve the effect of reducing the scale of the problem. Then continue to look for the target element within the possible range. This approach is suitable for complex problems. For example, if you’re looking for elements in an array that might not exist, if you’re looking for boundary problems, you can use this idea.

The resources

  • [Blog post] Learning — Algorithms — With — Leetcode — Section 3.1 binary Search Algorithms
  • [blog] dichotomy details plus details you really should understand!! _ Pony’s blog
  • 【 course 】 Zero-start Algorithm – LeetBook – Basic idea of binary search: Subtract and cure
  • Binary search algorithm details, incidentally wrote a poem – LeetCode