【Sword Pointing Offer】Dichotomy Example Questions

Hits: 0

[dichotomy]

I. Introduction

The linked list is an important chapter in the data structure, and its importance is self-evident. In the future, whether it is a written test or an interview, we will encounter such questions, so I will list all the frequently asked questions about the linked list. Sort it out for everyone to learn and correct.

2. Learning to brush the question website

Click the link below to learn

3. Brush questions

<1> Find the peak

topic link

describe:

Given an array nums of length n, find the peak and return its index. The array may contain multiple peaks, in which case return the location of any one of them.
1. A peak element is an element whose value is strictly greater than its left and right neighbors. Strictly greater than i.e. cannot have equal to
2. Suppose nums[-1] = nums[n] = −∞
3. For all valid i have nums[i] != nums[i + 1]
4. You can use O( logN) time complexity to achieve this problem?

data range:

1≤nums.length≤2×10^5
−2 ^31<=nums[i]<=2 ^31−1

For example, when inputting [2,4,1,2,7,8,4], two peaks will be formed, one is the peak with index 1 and peak value 4, and the other is the peak with index 5 and peak value 8. As shown below:

Example 1

Input: [2, 4, 1, 2, 7, 8, 4]
Return value: 1
Description: 4 and 8 are both peak elements, and either index 1 of 4 or index 5 of 8 can be returned

Example 2

Input: [1,2,3,1]
Return value: 2
Explanation: 3 is the peak element, return its index 2

Idea analysis:
The property of binary search is used here, because both sides of the array are infinitely small, so we can find the wave crest as long as we look up. Then we can find an element, divide the array into two intervals, go to the higher side each time, and finally lock a wave peak.

int findPeakElement(int* nums, int numsLen ) {
    // write code here
    int left = 0, right = numsLen - 1;
    while(left < right)
    {
        int mid = (left + right) / 2 ;
         //The right side is down, not necessarily a slope 
        if (nums[mid] > nums[mid + 1 ])
        {
            right = mid;
        }  
        //The right side is up, you must find the crest 
        else
        {
            left = mid + 1;
        }
    }
    return left;
}

<2> Search in two-dimensional array

Topic link
description:

In an array of two-dimensional arrays (each one-dimensional array of the same length), each row is sorted in ascending order from left to right, and each column is sorted in ascending order from top to bottom. Please complete a function, input such a two-dimensional array and an integer, and determine whether the array contains the integer.
[ [1,2,8,9]
,
[2,4,9,12],
[4,7,10,13],
[6,8,11,15]
]
Given target = 7, return true.
Given target = 3, return false.

Data range: The length and width of the matrix satisfy 0≤n, m≤500, and the values ​​in the matrix satisfy 0≤val≤10^9
Advanced: [space complexity] O(1)O(1), time complexity O(n+ m)O(n+m)

Example 1

Input: 7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
Return value: true
Description : 7 exists, returns true

Example 2:

Input: 1,[[2]]
Return value: false

Example 3

Input: 3,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
Return value: false
Description : does not exist 3, returns false

① Linear search

The simplest method is brute force traversal, which does not use the incremental nature of two-dimensional arrays.
Through the rule, it is found that the row where the element in the lower left corner is located is the smallest and the column in which it is located is the largest, then if the target is less than the element, let the row --, otherwise let the column ++.

bool Find(int target, int** array, int arrayRowLen, int* arrayColLen ) {
    // write code here
    int row = arrayRowLen - 1, col = 0;
    while(row <= arrayRowLen - 1 && row >= 0 && col <= *arrayColLen - 1 && col >= 0)
    {
        if(array[row][col] == target)
        {
            return true;
        }
        else
        {
            if(array[row][col] < target)
            {
                col++;
            }
            else
            {
                row--;
            }
        }
    }
    return  false ;
}

② Divide line by line

Because each row is sequentially increasing, each row can be divided into two

bool binary_search(int* arr, int k, int target)
{
    int left = 0, right = k - 1;
    while (left <= right)
    {
        int mid = (right + left) / 2;
        if (arr[mid] == target)
        {
            return true;
        }
        else if (arr[mid] > target)
        {
            right = mid - 1;
        }
        else
        {
            left = mid + 1;
        }
    }
    return  false ;
}



bool Find(int target, int** array, int arrayRowLen, int* arrayColLen) {
    // write code here
    for (int i = 0; i < arrayRowLen; i++)
    {
        if (binary_search(array[i], *arrayColLen, target))
        {
            return true;
        }
    }
   /*while (arrayRowLen--)
    {
        if (binary_search(*array, *arrayColLen, target))
        {
            return true;
        }
        array++;
    }*/ 
    return  false ;
}

<3> Minimum number of rotation array

topic link

describe:

There is a non-descending array of length n, such as [1,2,3,4,5], rotate it, that is, move the first elements of an array to the end of the array to become a rotated array, For example, it becomes [3,4,5,1,2], or [4,5,1,2,3]. Excuse me, given such a rotated array, find the minimum value in the array.

Data range: 1≤n≤10000, the value of any element in the array: 0≤val≤10000
Requirements: Space complexity: O(1)O(1), Time complexity: O(logn)O(logn)

Example 1:

Input: [3,4,5,1,2]
Return value: 1

Example 2:

Input: [3,100,200,3]
Return Value: 3

Analysis of ideas: This
question is actually a deformation of the dichotomy.The elements to the left of the rotation point are all monotonically increasing and are larger than the elements to the right of the rotation point that are monotonically increasing.
Our purpose is to find the rotation point, which is the smallest element. We can define the left left and right right pointers so that they meet at the rotation point: at that time
, it means that the mid must be inarr[mid] > arr[right]
left increasing interval, in order to make the left move to the rotation point, the interval needs to be reduced. At that timeleft = mid + 1
, it means that the mid must be inarr[mid] < arr[right]
right increasing interval, in order to move the right to the rotation point, the interval needs to be narrowed, right = mid
but there are also cases of the same elements, for example,{1,0,1,1,1}
it is impossible to determine which interval the mid is in.
Then let right--it. Left++ cannot be used here, because we are comparing with the rightmost element, and the rotation point must be to the left of mid.

int minNumberInRotateArray(int* arr, int sz ) {
    // write code here
    if(sz == 0)
    {
        return 0;
    }
    int left = 0, right = sz - 1;
    while(left < right)
    {
        int mid = (left + right) / 2;
        if(arr[mid] > arr[right])
        {
            left = mid + 1;
        }
        else if(arr[mid] < arr[right])
        {
            right = mid;
        }
        else
        {
            right--;
        }
    }
    return arr[left];
}

You may also like...

Leave a Reply

Your email address will not be published.