Binary search

What is binary search? Binary search is to continuously find the midpoint of the current sequence. By comparing with binary, if satisfied, the solution must be in the other half of the sequence, split the sequence in two, continue to search in the other half, and so on and so on, thus reducing the general search space each time, to achieve the time complexity of Ologn.

Secondary sex

The most important thing about binary search is that you have to have duality. What is duality? The first part of the sequence must satisfy one property and the second part does not, so we can find the intermediate point of the transformation of the two properties by binary search. For example, if we look for a number target=4 in s=[1,2,3,4,5], we can find a binary character in s, some of which are greater than target and some of which are less than target. Therefore, we need to find the point at which the property transformation is satisfied, that is, target. Another example is the test problem, a sequence, after the test fails at one point, all the following points are failures, let’s find the first point that fails, and this is also binary, because the first point that fails is successful before the first point, and all the following points fail, so the properties of the two sections are different. For sequences with two-segment properties, we can use binary search, and the time complexity can reach O(logn).

Binary search code and logic

Binary search code can have a lot of writing, here we introduce only two kinds, one kind is on the left, one on the left on the right of the mean, in choosing a halfway point, if the length is even, then click on the location of the left, in this time, if there is a repeat of the target, then code eventually selected on the left is the most on the left side of the same target. The same goes for the right:

l=0
r=n-1
while l<r:
	mid=(l+r+1) > >1
	ifWhether r=mid- satisfies one of the two properties1 
	else:
		l=mid
Copy the code

Because I’m picking right, if the answer that I’m picking doesn’t satisfy the property, I’m only going to look at the first half of mid

On the left:

l=0
r=n-1
while l<r:
	mid=(l+r)>>1
	ifWhether l=mid+ satisfies one of the two paragraphs1 
	else:
		r=mid
Copy the code

Because it’s left, if you don’t get the right half of mid, then the binary search code ends up at l=r

Examples of actual combat

1. Search for target in an ascending nums array. If a target is found, if not, return -1

class Solution(object) :
    def search(self, nums, target) :
        """ :type nums: List[int] :type target: int :rtype: int """
        l=0
        r=len(nums)-1
        while l<r:
            mid=(l+r+1) > >1
            if nums[mid]<=target:
                l=mid
            else:
                r=mid-1
        if nums[r]==target:
            return r
        else:
            return -1
Copy the code

Here, the dichotomy of our judgment is reflected in that, if the selected midpoint number is greater than target, target can only appear on the left of the midpoint, so r=mid-1, and the search continues on the left half

2. Suppose you have n versions [1, 2… n] and you want to find the first incorrect version that causes all subsequent versions to fail.

   You can tell if version failed in unit tests by calling the bool isBadVersion(version) interface. Implement a function to find the first incorrect version. You should minimize the number of calls to the API.

   The solution is that one version is wrong, all the subsequent versions are wrong, let’s find the first version that is wrong, it’s obviously binary, so consider binary search

class Solution:
    def firstBadVersion(self, n) :
        """ :type n: int :rtype: int """
        l=0
        r=n-1
        while l<r:
            mid=(l+r)>>1
            if isBadVersion(mid+1):
                r=mid
            else:
                l=mid+1
        return r+1
Copy the code

Here, we judge the second paragraph based on the fact that we are looking for the first error version, so we choose the left approach to determine whether the midpoint is wrong. If so, the current point may also be the first error, so we search from the left side containing the point, so r=mid note: We use the index 0-n-1 in the code, so the final output version is increased by 1, and the intermediate judgment version is also increased by 1

So why not go to the right? Here we consider that, since we are looking for the first incorrect version, the answer itself is to continue the search. If we choose the code on the right, the sequence will not be evenly divided and the speed will decrease. If we choose the code on the right, our dichotomy condition will change. The point you’re looking for should be the point before the first error point, which is the last successful point.

3. Count the number of occurrences of a number in a sorted array. Nums not decline

A classic dichotomy, this problem uses our nature, we can consider the use of left and right at the same time, respectively find the corresponding target far left and far right, and then subtract to get the frequency of target

class Solution(object) :
    def search(self, nums, target) :
        """ :type nums: List[int] :type target: int :rtype: int """
        if len(nums)==0:
            return 0
        l=0
        r=len(nums)-1
        while l<r:
            mid=(l+r+1) > >1
            if nums[mid]<=target:
                l=mid
            else:
                r=mid-1
        ifnums[r]! =target:return 0
        right=r

        l=0
        r=len(nums)-1
        while l<r:
            mid=(l+r)>>1
            if nums[mid]<target:
                l=mid+1
            else:
                r=mid

        return right-l+1
Copy the code

There’s nothing to talk about in this question, but can you draw a picture of that condition, and make sure it’s evenly divided

4. All numbers in an incrementally sorted array of length n-1 are unique, and each number is in the range 0 to n-1. Find one and only one of the n digits in the range 0 to n-1 that is not in the array.

Solution, this problem is obviously also be binary search, but 2 conditions difficult to think, first of all we want to know the length of the array in the 0 – n – 1 n – 1 data range and increasing, missed a number, so we know very easily, front part Numbers are missing Numbers and the subscript of the same, the back part and the subscript is different, so consider binary

class Solution(object) :
    def missingNumber(self, nums) :
        """ :type nums: List[int] :rtype: int """
    

        l=0
        r=len(nums)-1
        if nums[0] = =1:
            return 0
        
        while l<r:
            mid=(l+r+1) > >1
            ifnums[mid]! =mid: r=mid-1
            else:
                l=mid
        return nums[r]+1
Copy the code

If nums[mid] is the first digit to the left of the missing digit, it will return 0 if nums[mid]! So if I say =mid, the current midpoint is already the wrong point, so let’s think about r=mid-1, which is the first part. So what we end up finding is the number to the left of the missing number, so we need +1

5. The integer array NUMs is sorted in ascending order, with different values in the array.

   Before passing to the function, nums is rotated on some previously unknown subscript k (0 <= k < nums.length), Make the array [nums [k], nums [k + 1),…, nums] [n – 1, nums [0], nums [1],…, nums [k – 1]] (subscript starting from 0). ,1,2,4,5,6,7 [0], for example, in the subscript 3 after rotation may become,5,6,7,0,1,2 [4].

   Give you the rotated array nums and an integer target, return its subscript if nums contains the target value, otherwise -1

The solution, this is a little bit harder, first of all we need to find the point of rotation, because the points of rotation are ordered on both sides so first of all we need to think about bisection to find the point of rotation, how do we find the point of rotation? Where is the two-paragraph sex? For example, the array [1,2,3,4,5,6,7] becomes [5,6,7,1,2,3,4] after being rotated at some point, then we find that the rotation point is 5, but the orderly split point between the two segments is 1. Then we find that the 5,6,7 before the point 1 must be greater than or equal to 5 because it is rotated. We also find that 1234 must be less than 5 (because the values in the original array are different), so the dichotomy is that one part of nums[I]>=nums[0] (here is the rotated array) and the other part is the opposite. So first we find the point of rotation bisection. Code:

class Solution(object) :
    def search(self, nums, target) :
        """ :type nums: List[int] :type target: int :rtype: int """
        
        slen=len(nums)
        if slen == 0:
            return -1
        if slen ==1:
            if nums[0]==target:
                return 0
            else:
                return -1

        l=0
        r=slen-1
        while l<r:
            mid=(l+r+1) > >1
            if nums[mid]>nums[0]:
                l=mid
            else:
                r=mid-1
Copy the code

Now we have l=r= one point in front of the rotation point, which is the largest element in the array so we need to determine whether the target is in front of or behind the rotation point

		if target>=nums[0]:
		            l=0		      
		        else:
		            l=l+1
		            r=slen-1
Copy the code

If target is greater than nums[0], then it should be [0-r], where r is the location of the largest element. Otherwise, the last binary is searched from [L +1,slen-1]. Find a target in an ordered array

		while l<r:
            mid=(l+r+1) > >1
            if nums[mid]<=target:
                l=mid
            else:
                r=mid-1

        if nums[r]==target:
            return r
        else:
            return -1
Copy the code

Good today’s dichotomy is introduced here, if there is a problem, comment on it!