In order to find

If you were asked to find the book you wanted on a stack of shelves, how would you do it?

In fact, the simplest and most brutal way is to read through them.

This is the computer equivalent of sequential lookup.

concept

Sequential lookup is suitable for linear tables that store sequential storage or linked storage.

Basic idea: sequential search is also called linear search, belongs to the disordered search algorithm. Start from one end of the linear table of data structure, scan in sequence, compare the scanned node keywords with the given value K in turn, if they are equal, the search is successful; If no node whose keyword is k is found after the scan, the search fails.

Complexity analysis:

The average search length for successful searches is :(assuming equal probability for each data element) ASL = 1/n(1+2+3+… +n) = (n+1)/2 ;

If the search fails, n+1 comparisons are required, and the time complexity is O(n).

So, the time complexity of sequential lookup is O(n).

Java code implementation

Take Java code as an example:

/* ** sequential query algorithm ** @param arr array information ** @param target value ** @param arrLength array length */
int foreachSearch(int arr[], int target, int arrLength) {
    int i;
    for(i = 0; i < arrLength; i++) {
        if(target == arr[i]) {
            returni; }}return -1;
}
Copy the code

Java Improved Version

Our implementation version is mainly to make up for the shortcomings of most of the online implementation, many of the implementation is an int type, applicable scope is not wide enough.

The interface definition

For further extensibility, we define the query interface and abstract implementation.

package com.github.houbb.search.api;

import java.util.List;

/ * * *@authorThe old horse shouts the west wind@since0.0.1 * /
public interface ISearch<T> {

    /** * Execute the query for the element *@paramThe list list *@paramKey Target object *@returnThe result is subscript *@since0.0.1 * /
    int search(List<? extends Comparable<? super T>> list, T key);

}
Copy the code

Abstract implementation:

package com.github.houbb.search.core;

import com.github.houbb.heaven.util.common.ArgUtil;
import com.github.houbb.heaven.util.util.CollectionUtil;
import com.github.houbb.search.api.ISearch;
import com.github.houbb.search.constant.SearchConst;

import java.util.List;

/** * Abstract query class *@authorThe old horse shouts the west wind@since0.0.1 * /
public abstract class AbstractSearch<T> implements ISearch<T> {

    @Override
    public int search(List<? extends Comparable<? super T>> list, T key) {
        ArgUtil.notNull(key, "key");

        if(CollectionUtil.isEmpty(list)) {
            return SearchConst.NOT_FOUND;
        }

        return this.doSearch(list, key);
    }

    /** * Execute query *@paramThe list list *@param key key
     * @returnResults *@since0.0.1 * /
    protected abstract int doSearch(List<? extends Comparable<? super T>> list, T key);

}
Copy the code

Traverse the implementation

The implementation is similar to the previous base version.

package com.github.houbb.search.core;

import com.github.houbb.search.constant.SearchConst;

import java.util.List;

/** * traversal query method *@authorThe old horse shouts the west wind@since0.0.1 * /
public class ForeachSearch<T> extends AbstractSearch<T> {

    @Override
    @SuppressWarnings("all")
    protected int doSearch(List<? extends Comparable<? super T>> list, T key) {
        for(int i = 0; i < list.size(); i++) {
            Comparable comparable = list.get(i);
            if(comparable.compareTo(key) == 0) {
                returni; }}returnSearchConst.NOT_FOUND; }}Copy the code

The scope of this implementation has been deliberately narrowed down to comparable types, but it could be much broader, theoretically any object that can be compared via equals().

In fact, mainly in order to compatible with the following we want to talk about binary search method, but also the focus of our article.

Binary search method

Traversing queries is very simple and crude, but performance is also poor.

If the data you’re looking for has already been sorted, like when you’re looking for contacts, you can usually get a quick overview of the location by name, rather than going through it all.

This is the binary search method implemented by computer.

concept

Dsmt4 search (BINARY search), also known as half-interval search, logarithmic search, is a search algorithm that looks for a specific element in an ordered array.

The search process starts with the middle element of the array, and ends if the middle element is exactly the element being searched.

If a particular element is greater than or less than the middle element, it looks in the half of the array that is greater than or less than the middle element, and compares from the middle element as it began.

If the array is empty at any step, it cannot be found. This search algorithm reduces the search area by half with each comparison.

Complexity Overview

classification	Search algorithm
The data structure	An array of
Worst time complexity	O(log(n))
Optimal time complexity	O(1)
Average time complexity	O(log(n))
Spatial complexity	Iterations: O (1); Recursive: O (log (n))

steps

(1) First determine the middle position of the entire search interval mid = (left + right) / 2

(2) Compare the keyword value to be searched with the keyword value in the middle position;

If they are equal, the search succeeds

If it is greater than, the split search continues in the back (right) half of the region

If less than, the split search continues in the first (left) half of the region

(3) Repeat the above steps according to the semicolon formula for the defined reduced area.

Finally, you get the result: either the search succeeds or the search fails.

The storage structure of split – half search is one-dimensional array.

Note: One prerequisite is that the array must be ordered. What if the element is out of order? Do the sort first, of course, and then do the half search.

Sorting algorithm is not the focus of this article, you can refer to:

In 7 days, I sorted out and implemented the 9 most classic sorting algorithms

Java code implementation

Let’s start by looking at two of the most common implementations on the web.

The recursive implementation

public static int binarySearch(int[] arr, int start, int end, int hkey){
    if (start > end)
        return -1;

    int mid = start + (end - start)/2;    // Prevent overflow
    if (arr[mid] > hkey)
        return binarySearch(arr, start, mid - 1, hkey);
    if (arr[mid] < hkey)
        return binarySearch(arr, mid + 1, end, hkey);
    return mid;  

}
Copy the code

The version of the recursive implementation is very neat and elegant.

Cycle to achieve

public static int binarySearch(int[] arr, int start, int end, int hkey){
    int result = -1;

    while (start <= end){
        int mid = start + (end - start)/2;    // Prevent overflow
        if (arr[mid] > hkey)
            end = mid - 1;
        else if (arr[mid] < hkey)
            start = mid + 1;
        else {
            result = mid ;  
            break; }}return result;
}
Copy the code

A circular implementation is a bit more cumbersome, but generally performs better than recursion.

Java Improved Version

The above approach is very succinct, and the problem is equally obvious.

What if I want to compare and find strings, Long, and other common types?

We can modify the above implementation slightly:

package com.github.houbb.search.core;

import com.github.houbb.search.constant.SearchConst;

import java.util.List;

/** * half *@authorThe old horse shouts the west wind@since0.0.1 * /
public class BinarySearch<T> extends AbstractSearch<T> {

    @Override
    @SuppressWarnings("all")
    protected int doSearch(List<? extends Comparable<? super T>> list, T key) {
        int low = 0;
        int high = list.size()-1;

        while (low <= high) {
            int mid = (low+high) / 2;

            Comparable comparable = list.get(mid);
            if(comparable.compareTo(key) == 0) {
                return mid;
            } else if(comparable.compareTo(key) < 0) {
                // Less than the specified element
                low = mid;
            } else {
                // Greater than the specified elementhigh = mid; }}returnSearchConst.NOT_FOUND; }}Copy the code

Here we extend the comparison object to Comparable, and then compare it using the compareTo method.

Open source tools

Of course, the normal search algorithm ends here, but Ma doesn’t think so.

Know what it is, know why it is, so we’re going to learn how algorithms work.

A gentleman’s character is not different, good fake in things, so we have to learn to use tools.

Algorithms should be packaged as simple, usable tools that are easy to use. So Ma open source the above two query algorithms to maven’s central repository for later use and expansion.

Maven is introduced into

<dependency>
    <groupId>com.github.houbb</groupId>
    <artifactId>search</artifactId>
    <version>0.0.1</version>
</dependency>
Copy the code

use

Traverse the query

final List<String> list = Arrays.asList("1"."2"."3"."4"."5");
Assert.assertEquals(3, SearchHelper.foreach(list, "4"));
Copy the code

Binary query

final List<String> list = Arrays.asList("1"."2"."3"."4"."5");
Assert.assertEquals(3, SearchHelper.binary(list, "4"));
Copy the code

summary

Hope you found this article helpful, and if you have any other ideas, please share them in the comments section.

All geeks’ likes, favorites and forwarding are the biggest motivation for Lao Ma to continue writing!

In the next section, we will explain the binary query tree, interested partners can pay attention to a wave of wonderful content, not to be missed.