Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

This article also participated in the “Digitalstar Project” to win a creative gift package and creative incentive money

The search algorithm question is a kind of question which is often examined in the written interview.

1. Lookup in a two-dimensional array

describe

In a two-dimensional array array (each one-dimensional array is 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. Complete a function that takes such a two-dimensional array and an integer and determines whether the integer is in the array.

,4,9,12,2,8,9 [[1], [2], [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 are 0≤n,m≤5000, and the values in the matrix are 0≤ Val ≤10^9.

Example 1

Input:

7, [,2,8,9 [1], [2,4,9,12],,7,10,13 [4], [6,8,11,15]]Copy the code

The return value:

true
Copy the code

Description:

If 7 exists, return trueCopy the code

Example 2

Input:

1, [[2]]Copy the code

The return value:

false
Copy the code

Example 3

Input:

,2,8,9 3, [[1], [2,4,9,12],,7,10,13 [4], [6,8,11,15]]Copy the code

The return value:

false
Copy the code

Description:

If 3 does not exist, return falseCopy the code

Answer key 1

Violent binary search:

For n rows, binary search is used for each row to find target. If a row is found, return true. If none is found, return false.

Time complexity :O(n*logm)

Space complexity :O(1)

public class Solution {
    public boolean Find(int target, int [][] array) {
        if(array.length == 0) {return false;
        }
        for(int[] arr : array){
            if(arr.length == 0) {return false;
            }
            if(arr[0] <= target){
                boolean ans = binarySearch(target,arr);
                if(ans == true) {return true; }}}return false;
    }
    
    public boolean binarySearch(int target, int[] arr){
        int left = 0;
        int right = arr.length - 1;
        while(left <= right){
            int mid = left + (right-left)/2;
            if(arr[mid] > target){
                right = mid - 1;
            }else if(arr[mid] < target){
                left = mid+1;
            }else{
                return true; }}return false; }}Copy the code

Solution 2 Search from the lower left corner (same with the upper right corner)

Using the properties of the two-dimensional array:

  • Each row is sorted in ascending order from left to right,
  • Each column is sorted in ascending order from top to bottom

Let’s take the value leftDown from the bottom left corner. The value can be the smallest value in the line or the maximum value in the column.

  1. When the value of leftDown is < target, the value should be pushed right by one value since m is already the largest element in the line
  2. When the value of leftDown > target, since M is already the smallest element in the column, the only way to get smaller is to move the value up one value from the row
  3. Return true when leftDown = target is found

A row minimum or column maximum can be compared to target to exclude an entire row or column at a time

public class Solution {
    public boolean Find(int target, int [][] array) {
        int rows = array.length;
        if(rows == 0) {return false;
        }
        int cols = array[0].length;
        if(cols == 0) {return false;
        }
        int i = rows-1;
        int j = 0;
        while(i>=0 && j<=cols-1) {int leftDown = array[i][j]; // The value in the lower left corner
            if(leftDown > target){
                i -= 1;
            }else if(leftDown < target){
                j += 1;
            }else{
                return true; }}return false; }}Copy the code

conclusion

Solution 2 is mainly due to the particularity of the matrix in this problem. In the future, when a certain step of the problem is searched for a certain value, we can use binary search as in solution 1, with the complexity O(logn)< linear search O(n).

2.Rotate the smallest number in the array

describe

Take a non-descending array of length n, such as [1,2,3,4,5], and rotate it by moving the beginning elements to the end of the array to create a rotated array, such as [3,4,5,1,2,3] or [4,5,1,2,3]. Given such a rotation array, find the minimum value in the array.

Data range: 1≤n≤10000, value of any element in the array: 0≤val≤100000

Requirements: Space complexity: O(1), time complexity: O(logn)

Example 1

Input:

,4,5,1,2 [3]Copy the code

The return value:

1
Copy the code

Example 2

Input:

[3100200]Copy the code

The return value:

3
Copy the code

Answer key

The main use of dichotomy, divided into the following situations:

  • [1,2,3,4,5] increments in order to output 1
  • ,4,5,1,2 [3] in the first round: low = 0, high = 4, mid = 2 to 5, 5 > 2, low pointer should be moved to the right mid + 1 = 3, point 1. Array [low=3] < array[high=4], mid=3 For round 3, low= High, return array[LOW]=1.
  • [2,0,2,2,2] first round: Low =0, high=4, mid=2 points to 2, note that in particular array[mid]=array[high]=array[low], so you can’t tell whether the minimum is to the left or right of mid, we did low++ to narrow it down. Array [low]
import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
       int low = 0;
       int high = array.length - 1;
       while(low < high){
           if(array[low] < array[high]){ // [1,2,3,4,5
               return array[low];
           }
           int mid = low + (high - low)/2;
           if(array[mid] > array[high]){
               low = mid + 1;
           }else if (array[mid] < array[high]){
               high = mid;
           }else{ low++; }}returnarray[low]; }}Copy the code

End summary

The basic dichotomy template is as follows, and many questions are modified on this basis.

    public boolean binarySearch(int target, int[] arr){
        int left = 0;
        int right = arr.length - 1;
        while(left <= right){
            int mid = left + (right-left)/2;
            if(arr[mid] > target){
                right = mid - 1;
            }else if(arr[mid] < target){
                left = mid+1;
            }else{
                return true; }}return false;
    }
Copy the code