Algorithm must brush series search and sorting

Article directory

• binary search
• • sequential search
  • Binary search iteration writing method
  • Binary search recursive writing
  • Binary search for duplicate elements in elements
  • Find first and last position of element in sorted array
  • Peak index of mountains array
  • Minimum number for rotating numbers
  • Find missing numbers
  • Optimize square root
  • Search for a specified value in a binary search tree
  • Verify binary search tree
  • Convert ordered array to binary search tree
• Quick sort
• • Implement quick sort based on the first element
  • Quick sort based on the last element
  • Quick sort based on the middle element
• merge sort
• • merge sort

Binary search

Sequential search

Traverse one by one to determine whether it is the element to be found

public int search(int[] array,int key){<!-- -->
    for(int i=0;i<array.length;i + + ){<!-- -->
        if(array[i]==key){<!-- -->
            return i;
        }
    }
    return -1;
}

Binary search iteration writing method

Ordered arrays are available and can be used as template memories, please pay attention to the boundaries

public int binarySearch(int[] array,int key,int low,int high){<!-- -->
    while (low<= high){<!-- -->
        int mid = low + ((high-low)>>1);
        if(array[mid]==key){<!-- -->
            return mid;
        }else if(array[mid]>key){<!-- -->
            high = mid - 1;
        }else if(array[mid]<key){<!-- -->
            low = mid + 1;
        }
    }
    return -1;
}

Binary search recursive writing

Ordered arrays are available and can be used as template memories, please pay attention to the boundaries

public int binarySearch(int[] array,int key,int low,int high){<!-- -->
    if(low<=high){<!-- -->
        int mid = low + ((high-low)>>1);
        if(array[mid]==key){<!-- -->
            return mid;
        }else if(array[mid]>key){<!-- -->
            return binarySearch(array,key,low,mid-1);
        }else if(array[mid]<key){<!-- -->
            return binarySearch(array,key,mid + 1,high);
        }
    }
    return -1;
}

Binary search for duplicate elements in elements

After finding the element based on the template, continue to traverse forward to find the position equal to the first occurrence of the element to be found in the array. If there are too many elements, you can also use binary search to continue searching

public int binarySearchRe(int[] array, int key, int low, int high) {<!-- -->
    while (low <= high) {<!-- -->
        int mid = low + ((high - low) >> 1);
        if (array[mid] == key) {<!-- -->
            while (mid >= 0 & amp; & amp; array[mid] == key) {<!-- -->
                mid--;
            }
            return mid + 1;
        } else if (array[mid] > key) {<!-- -->
            high = mid - 1;
        } else if (array[mid] < key) {<!-- -->
            low = mid + 1;
        }
    }
    return -1;
}

Find the first and last position of an element in a sorted array

After finding the element based on the template, continue to traverse forward and backward to find the position equal to the first occurrence and the last occurrence of the element to be found in the array. If there are too many elements, you can also use binary search to continue searching

public int[] searchRange(int[] nums, int target) {<!-- -->
    return binarySearch(nums,target,0,nums.length-1);
}

public int[] binarySearch(int[] nums,int target,int low,int high){<!-- -->
    int[] res = new int[]{<!-- -->-1,-1};
    while(low<=high){<!-- -->
        int mid = low + ((high-low)>>1);
        if(nums[mid]==target){<!-- -->
            int left = mid;
            while(left>=0 & amp; & amp;nums[left]==target){<!-- -->
                left--;
            }
            int right = mid;
            while(right<nums.length & amp; & amp;nums[right]==target){<!-- -->
                right + + ;
            }
            res[0] = left + 1;
            res[1] = right-1;
            return res;
        }else if(nums[mid]>target){<!-- -->
            high = mid-1;
        }else if(nums[mid]<target){<!-- -->
            low = mid + 1;
        }
    }
    return res;
}

Peak index of mountain array

Note that the judgment conditions for mountains are higher than the data on both sides. The increasing order is on the left and the decreasing order is on the right

public int peakIndexInMountainArray(int[] arr) {<!-- -->
    int high = arr.length-2;
    int low = 1;
    while(low <= high){<!-- -->
        int mid = low + ((high-low)>>1);
        if(arr[mid]>arr[mid-1] & amp; & amp; arr[mid]>arr[mid + 1]){<!-- -->
            return mid;
        }else if(arr[mid]>arr[mid-1] & amp; & amp; arr[mid]<arr[mid + 1]){<!-- -->
            low = mid + 1;
        }else if(arr[mid]<arr[mid-1] & amp; & amp; arr[mid]>arr[mid + 1]){<!-- -->
            high = mid - 1;
        }
    }
    return -1;
}

The smallest number to rotate the number

Use binary search template, boundary value is determined by test sample

public int findMin(int[] nums) {<!-- -->
    int low = 0;
    int high = nums.length - 1;
    while(low<high){<!-- -->
        int mid = low + ((high-low)>>1);
        if(nums[mid]>nums[high]){<!-- -->
            low = mid + 1;
        }else if(nums[mid]<nums[high]){<!-- -->
            high = mid;
        }
    }
    return nums[low];
}

Find missing numbers

Use binary search template, boundary value is determined by test sample

public int missingNumber(int[] array){<!-- -->
    int high = array.length;
    int low = 0;
    while (low<=high){<!-- -->
        int mid = low + ((high - low)>>1);
        if(array[mid] == mid){<!-- -->
            low = mid + 1;
        }else{<!-- -->
            high = mid - 1;
        }
    }
    return low;
}

Optimizing the square root

Use binary search template, boundary value is determined by test sample

public int mySqrt(int x) {<!-- -->
    int low = 1;
    int high = x;
    while(low <= high){<!-- -->
        int num = low + ((high-low)>>1);
        if(x/num == num){<!-- -->
            return num;
        }else if(x/num>num){<!-- -->
            low = num + 1;
        }else{<!-- -->
            high = num - 1;
        }
    }
    return high;
}

Search for the specified value in the binary search tree

The combination of binary search and binary tree, first determine the root node, and then search in the left subtree or right subtree according to the root node and the value to be searched

public TreeNode searchBST(TreeNode root, int val) {<!-- -->
    if(root==null){<!-- -->
        return null;
    }else if(root.val == val){<!-- -->
        return root;
    }else if(root.val<val){<!-- -->
        return searchBST(root.right,val);
    }else if(root.val>val){<!-- -->
        return searchBST(root.left,val);
    }
    return null;
}

Verify binary search tree

Limit low and high to two ranges for verification. When verifying the left and right subtrees, update low and high according to the value of the root node.

public boolean isValidBST(TreeNode root) {<!-- -->
    long low = Long.MIN_VALUE;
    long high = Long.MAX_VALUE;
    return isValidBST(root,low,high);
}

public boolean isValidBST(TreeNode root,long low,long high){<!-- -->
    if(root==null){<!-- -->
        return true;
    }
    if(root.val<=low || root.val >=high){<!-- -->
        return false;
    }
    return isValidBST(root.left,low,root.val) & amp; & amp;isValidBST(root.right,root.val,high);
}

Convert an ordered array into a binary search tree

Each time, select the middle value as the root node, and then create the left and right subtrees through the left and right sequences

public TreeNode sortedArrayToBST(int[] nums) {<!-- -->
    return sortedArrayToBST(nums,0,nums.length-1);
}

public TreeNode sortedArrayToBST(int[] nums,int left,int right){<!-- -->
    if(left>right){<!-- -->
        return null;
    }
    int mid = left + ((right-left)>>1);
    TreeNode root = new TreeNode(nums[mid]);
    root.left = sortedArrayToBST(nums,left,mid-1);
    root.right = sortedArrayToBST(nums,mid + 1,right);
    return root;
}

Quick sort

Quick sort based on the first element

Quick Sort Template 1

public void quickSort(int[] array, int left, int right) {<!-- -->
    if(left<right){<!-- -->
        int pivot = array[left];
        int i = right + 1;
        for (int j = right; j > left; j + + ) {<!-- -->
            if (array[j] > pivot) {<!-- -->
                i--;
                int temp = array[j];
                array[j] = array[i];
                array[i] = temp;
            }
        }
        int pivotIndex = i - 1;
        int temp = array[left];
        array[left] = array[pivotIndex];
        array[pivotIndex] = temp;
        quickSort(array,left,pivotIndex-1);
        quickSort(array,pivotIndex + 1,right);
    }
}

Quick sort based on the last element

Quick Sort Template 2

public void quickSort(int[] array, int left, int right) {<!-- -->
    if (left < right) {<!-- -->
        int pivot = array[right];
        int i = left - 1;
        for (int j = left; j < right; j + + ) {<!-- -->
            if (array[j] < pivot) {<!-- -->
                i + + ;
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
        int pivotIndex = i + 1;
        int temp = array[pivotIndex];
        array[pivotIndex] = array[right];
        array[right] = temp;
        quickSort(array, left, pivotIndex - 1);
        quickSort(array, pivotIndex + 1, right);
    }
}

Quick sorting based on the middle element

Quick Sort Template 3

public static void quickSort(int[] array, int start, int end) {<!-- -->
    if (start >= end) {<!-- -->
        return;
    }
    int left = start;
    int right = end;
    int mid = (left + right) / 2;
    int pivot = array[mid];
    while (left <= right) {<!-- -->
        while (left <= right & amp; & amp; array[left] < pivot) {<!-- -->
            left + + ;
        }
        while (left <= right & amp; & amp; array[right] > pivot) {<!-- -->
            right--;
        }
        if (left <= right) {<!-- -->
            int temp = array[left];
            array[left] = array[right];
            array[right] = temp;
            left + + ;
            right--;
        }
    }
    quickSort(array, start, right);
    quickSort(array, left, end);
}

Merge sort

Merge sort

Merge sort template

public void mergeSort(int[] array, int start, int end, int[] temp) {<!-- -->
//2. Stop dividing until each sequence contains only one element.
    if (start >= end) {<!-- -->
        return;
    }
    //1. Starting from the middle, divide it into two sequences each time
    mergeSort(array, start, (start + end) / 2, temp);
    mergeSort(array, (start + end) / 2 + 1, end, temp);
    //3. Merge ordered arrays
    merge(array, start, end, temp);
}

public void merge(int[] array, int start, int end, int[] temp) {<!-- -->
//Find the midpoint of the sequence
    int mid = (start + end) / 2;
    //left traverses the sequence on the left
    int left = start;
    //right traverses the sequence on the right
    int right = mid + 1;
    //index traverses the temporary array and stores the merged results
    int index = 0;
    //Both sequences are traversed from the starting point to the end point
    while (left <= mid & amp; & amp; right <= end) {<!-- -->
    //Put the smaller element of the two sequences into a temporary array
        if (array[left] < array[right]) {<!-- -->
            temp[index + + ] =array[left + + ];
        }else {<!-- -->
            temp[index + + ] =array[right + + ];
        }
    }
    //At this time, there is only one sequence left that has not been traversed and assigned directly.
    while (left <= mid){<!-- -->
        temp[index + + ] =array[left + + ];
    }
    while (right<=end){<!-- -->
        temp[index + + ] =array[right + + ];
    }
    //Copy the merged result to the original array
    for (int i=start;i<=end;i + + ){<!-- -->
        array[i] = temp[i];
    }
}

The problem of the Kth largest number in an array can be solved by array sorting. Choose an appropriate sorting algorithm according to the time and space complexity given in the question