preface

Make a note of the search algorithm for learning. Search is to find a specific information element in a large amount of information, and the algorithm used to find some data in a container is the search algorithm.

Linear search

Given a lookup value, find the given value one by one in the lookup container.

Linear search is the simplest search algorithm.

Code implementation:

Create an array {1, 9, 24, 20, 16, 14, 265} to store data, go through the number group to compare and find the corresponding data, take out the coordinates of the data, and get the data.

package com.datastructure.search;

/ * * *@author Hacah
 * @date2020/11/10 22:08 * /
public class SeqSearch {

    public static void main(String[] args) {
        int[] arr = {1.9.24.20.16.14.265};
        int i = seqSearch(arr, 14);
        System.out.println(i);
    }

    /** * linear search, return the corresponding data in the array subscript *@paramArr finds the array *@paramSeaInt to find data *@return* /
    public static int seqSearch(int[] arr,int seaInt) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == seaInt) {
                returni; }}return -1; }}Copy the code

Binary search

Binary search is an efficient search method using the idea of divide and conquer. Take full advantage of the order relationships between elements.

Implement ideas

1. Array must be ordered, the array of data according to the middle number of two sections, judge less than, greater than, equal to, if equal to find.
2. If it’s greater than the middle, it’s to the right of the middle, if it’s less than the middle, it’s to the left.
3. Repeat the steps until you find the data.

Search algorithm is widely used in many scenarios. Compared with linear search, binary search is a good algorithm to reduce time consumption and improve efficiency.

Note: The prerequisite of split search is that the ordered table is stored in order. For the static search table, there is no change after sorting, so the split search can get good efficiency. However, it is not recommended for data sets that require frequent inserts or deletes where maintaining an ordered sort is a significant amount of work. — Big Talk Data Structure

Diagram to implement

Let’s say I want to find 16, and I define two variables left and right to store the left and right subscripts of an array

Left + right / 2 to get the median midIndex.

Compare midIndex with 16, and since 13 is less than 16, look to the left, as shown below.

We get (left + right) / 2 median midIndex is 4, so here’s the picture.

Compare midIndex with the searched data, the two numbers are equal, return data 16 subscript 4, complete the query.

Code implementation

Create array {11, 45, 5, 5, 945, 248, 52, 93, 945}, implement binary search algorithm to find the location of 945.

package com.datastructure.search;

import java.util.ArrayList;
import java.util.Arrays;

/ * * *@author Hacah
 * @date2020/11/12 22:57 * /
public class BinarySearch {

    public static void main(String[] args) {
        int[] arr = {11.45.5.5.945.248.52.93.945};
        Arrays.sort(arr);
        System.out.println(Arrays.toString(arr));
// int a = binarySearch(0, arr.length - 1, arr, 52);
// System.out.println(a);
        ArrayList arrayList = binarySearchs(0, arr.length - 1, arr, 945);
        System.out.println(arrayList);

    }


    /** * binary search method **@paramLeft Left pointer *@paramRight right pointer *@paramArray arr *@paramValue Indicates the search value */
    public static int binarySearch(int left, int right, int[] arr, int value) {
        int midIndex = (left + right) / 2;
        int midValue = arr[midIndex];

        if (left <= right) {
            if (value < midValue) {
                return binarySearch(left, midIndex - 1, arr, value);
            } else if (value > midValue) {
                return binarySearch(midIndex + 1, right, arr, value);
            } else if (value == midValue) {
                returnmidIndex; }}return -1;
    }


    /** * query multiple results *@param left
     * @param right
     * @param arr
     * @param value
     * @return* /
    public static ArrayList binarySearchs(int left, int right, int[] arr, int value) {
        int midIndex = (left + right) / 2;
        int midValue = arr[midIndex];

        if (left <= right) {
            if (value < midValue) {
                return binarySearchs(left, midIndex - 1, arr, value);
            } else if (value > midValue) {
                return binarySearchs(midIndex + 1, right, arr, value);
            } else if (value == midValue) {
                ArrayList<Integer> list = new ArrayList<>();
                list.add(midIndex);
                // The left side of midValue
                int temp = midIndex - 1;
                while (temp >= 0 && value == arr[temp]) {
                    list.add(temp);
                    temp--;
                }
                // The right side of midValue
                int tempR = midIndex + 1;
                while (tempR <= right && value == arr[tempR]) {
                    list.add(tempR);
                    tempR++;
                }
                returnlist; }}return null; }}Copy the code

Applicable scenario

• Binary search for a sequence with more elements
• The premise of binary search must be the order of the sequence, unordered need to sort, confirm whether the cost is consistent with the actual.