This is the 9th day of my participation in Gwen Challenge

Recently, I want to sort out my experience of brush algorithm. On the one hand, I want to review and consolidate. On the other hand, I also hope that my sharing can help more friends in learning algorithm.

The column is called “Algorithm Tips”, which will focus on the entirety of the algorithm, but will not cover all aspects. It is suitable for people with some algorithm experience to read.

This time we will focus on binary search, this part of all questions and source code are uploaded to github directory, mainly in Python.

The classical dichotomy

Let’s start with a classic dichotomy problem from Leetcode’s 704. binary search.

The algorithm is as follows:

  • Initialization pointerleft = 0, right = n - 1.
  • whenleft <= right:
    • Compare intermediate elementsnums[mid]And the target value target.
    • iftarget = nums[mid], return to Pivot.
    • iftarget < nums[mid], continue the search on the leftright = mid - 1.
    • iftarget > nums[mid], continue the search on the rightleft = mid + 1.

Go straight to Python code

class Solution:
    def search(self, nums: List[int], target: int) - >int:
        left, right = 0.len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid
            if target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        return -1
Copy the code

Mid = left + (right-left) // 2 (mid = left + (right-left) // 2)

For example, in Java, int ranges from -2^32 to 2^31, i.e. -2147483648 to 2147483647.

public class Test {
    public static void main(String[] args) {
        int end = Integer.MAX_VALUE;
        System.out.println(end+1); / / output - 2147483648}}Copy the code

Java and C++ require this consideration, but Python does not. Python’s integers have no size limit and can handle integers of any size, including negative integers of course.

Let’s take a code example, 2 to the 1000, and you’ll see that the answer has been calculated correctly.

See my Resources article for more details on how Python implements storing long integers.

The square root of x

Next, look at a variation on the dichotomy problem, which comes from the square root of leetcode’s 69.x.

So it’s pretty simple, implement int SQRT (int x). If there is a decimal, the decimal part is omitted, for example, input 8, output 2.

The lower bound of binary lookup is 0, and the upper bound can be roughly set to x. In each step of binary search, we only need to compare the relation between the square of mid and the size of x, and adjust the range of upper and lower bounds based on the result of comparison.

class Solution:
    def mySqrt(self, x: int) - >int:
        left, right = 0, x
        while left <= right:
            mid = (left + right) // 2
            if mid * mid == x:
                return mid
            if mid * mid < x:
                left = mid + 1
            else:
                right = mid - 1
        if left * left > x:
            return left -1
        else:
            return left
Copy the code

I used the binary lookup code template as a whole, with the extra determination of which left and left-1 should be returned when the final result is returned.

The other way to do it is, since we ended up with tails, we don’t have to try ans+1 after we get the final answer, ans+1.

class Solution:
    def mySqrt(self, x: int) - >int:
        l, r, ans = 0, x, -1
        while l <= r:
            mid = (l + r) // 2
            if mid * mid <= x:
                ans = mid
                l = mid + 1
            else:
                r = mid - 1
        return ans
Copy the code

This problem, while seemingly simple, is prone to error, especially with some boundaries, and if necessary run more test cases.

Search rotation sort array

Let’s move on to an updated version of binary search, 33. Search rotated sorted arrays

Although the array is rotated, the whole thing can be solved by binary lookup.

In conventional binary search, we can check which part [L, mid] and [mid + 1, r] of the two parts whose mid is currently separated from the split position are orderly, and determine how to change the upper and lower bounds of binary search according to the ordered part. Because we can tell if Target is in this part based on the ordered part

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

The resources

How to Implement Super-long Integers in Python