JDK learning search algorithm

2010-04-13  来源:本站原创  分类:Java  人气:164 

Today we learn of two commonly used search algorithms: sequential search and binary search, no BS, the first on the code, later analysis:

1. Here are two kinds of search algorithm, in which the second taken from the JDK source code:

Sequential search

public static int sequentialSearch(int[] arrays, int key) {
                // Declare an array subscript returned
                int index = -1;
                // Declaration for the flags, improve lookup
                boolean found = false;

                for (int i = 0; (i < arrays.length) & !found; i++) {
                        if (arrays[i] == key) {
                                found = true;
                                index = i;

                        }

                }

                return index;

        }

Binary search, taken from the JDK in Arrays.binarySearch (int [] a, int key):

public static int binarySearch(int[] a, int key) {
                                // Declare an array of minimum and maximum values
                        int low = 0;
                        int high = a.length-1;                  

                        while (low <= high) {
                                    // Go to low and  high And the index, the value assigned to the  midVal
                            int mid = (low + high) >> 1;
                            int midVal = a[mid];
                                    // Use midVal with  key Compare size, if less than  key, You will be assigned to mid + 1  low, If is greater than the key, you will
                             //mid-1 Assigned to the high, otherwise it is returned directly  mid( Equal to  key)
                            if (midVal < key)
                                low = mid + 1;
                            else if (midVal > key)
                                high = mid - 1;
                            else
                                return mid; // key found
                        }
                        return -(low + 1);  // key not found.
                    }

2. Typical applications:

Similarly, directly on the code:

public class ArraysTest {

        public static int sequentialSearch(int[] arrays, int key) {
                // Declare an array subscript returned
                int index = -1;
                // Declaration for the flags, improve lookup
                boolean found = false;

                for (int i = 0; (i < arrays.length) & !found; i++) {
                        if (arrays[i] == key) {
                                found = true;
                                index = i;

                        }

                }

                return index;  // key not found.;

        }

        public static void main(String[] args) {

                int[] compartorIntArray = new int[3];
                compartorIntArray[0] = 1;
                compartorIntArray[1] = 2;
                compartorIntArray[2] = 3;
                System.out.println(ArraysTest.sequentialSearch(compartorIntArray, 3));
                System.out.println(ArraysTest.sequentialSearch(compartorIntArray, 8));
                System.out.println(Arrays.binarySearch(compartorIntArray, 3));
                System.out.println(Arrays.binarySearch(compartorIntArray, 8));
        }

}

Implementation of the results:

2
-1
2
-4

3. Summary

We can see from on top, in order to find the minimum search time is O (1), the maximum search time is O (n), the average time complexity is ((n +1) / 2)

Here we should note that the binary search, to be used in an orderly linear array and is not linked, unordered array sort in advance before implementation,

The average time complexity is approximately log (2) [n +1] -1, than the sequential search of the ((n +1) / 2) is much more efficient.

NOTE: Many programmers for time complexity and space complexity of the concept is not very understanding, I learned a lot of time and read the books, here I propose

Please do not delve into its excessive, especially in doing business development programmer, probably best to remember the time complexity of each algorithm can be in practical applications

Reasonable choice, if it needs to study the proposed first review about mathematics.

相关文章
  • JDK learning search algorithm 2010-04-13

    Today we learn of two commonly used search algorithms: sequential search and binary search, no BS, the first on the code, later analysis: 1. Here are two kinds of search algorithm, in which the second taken from the JDK source code: Sequential search

  • By analyzing the source code of JDK red-black tree algorithm TreeMap 2011-05-04

    By analyzing the source code of JDK red-black tree algorithm TreeMap Li Gang , a freelance writer Introduction: TreeMap and TreeSet Java Collection Framework is two important members of the Map interface, which is commonly used TreeMap implementation

  • String search algorithm summary 2010-04-26

    Hash algorithm for online search of knowledge, they inadvertently found some string search algorithm. Before the study because some search algorithm, that should be classified as a class. So write an article on to record the learning process. Questio

  • [Original] JWFD workflow engine design - the node matching search algorithm (re-discussion) 2009-08-04

    JWFD workflow engine design - the node matching search algorithm (re-discussion) NMSA Node matching search algorithm - Node Matching Algorithm Description So, this is only to design an algorithm, because in the design flow engine encountered the foll

  • Binary search algorithm (binary search) principle and the recursive (recuition), iteration (iteration) of the two implementations of the source code 2010-03-18

    Binary search method is also known as binary search, which makes full use of the order of relations between elements, with sub-rule strategy can be used in the worst case O (log n) complete the search task. The basic idea] [ N number of elements will

  • Baidu search algorithm management 2010-07-19

    Search algorithm engineer incentive guess: the principle of each engineer to manage a set of algorithms, and fully in charge of this algorithm, including the algorithm of this method in all the weight of a person shall not interfere. Such as algorith

  • Search algorithm - binary search 2010-09-20

    Binary search is to use a wide range of search algorithm, can be used recursive and non recursive implementation. Binary search the most suitable conditions to meet the requirements the following requirements: 1, the source data must be orderly. 2, s

  • Massive data search algorithm - storage / query / sort algorithm 2010-09-28

    Original Address: http://www.ad0.cn/netfetch/read.php/1134.htm Massive database applications, such as the country's population management system, household registration records management system, in such a massive database applications, database desi

  • Website Optimization relationship with Baidu search algorithm 2010-10-21

    Website Optimization relationship with Baidu Baidu search search algorithm, a very smart search profit institutions. I have repeatedly mentioned Bowen Baidu, said the truth, hated Baidu. This kind of hate, of course, does not rule out the identity as

  • String search algorithm 2011-01-10

    Copyleft this document owned by yfydz all, the use of GPL, free to copy, reprint, reproduced keep the documents for completeness, for any commercial purposes is strictly prohibited. msn: [email protected] Source: http://yfydz.cublog.cn References

  • Static search algorithm 2011-05-28

    Static search algorithm: only the lookup table lookup operation does not change the table First, the sequential search Algorithm idea: starting from one end of the table, one by one to the other end of the reference value by comparing the keyword kx,

  • The initial binary search algorithm 2010-05-10

    Never seriously studied data structure, has never written anything decent algorithm, is destined to go the way of my programmers is very difficult, is the time for a change, so the next time will start from the ground by learning, accumulated bit by

  • Fun of the python binary search algorithm of 2010-05-04

    # -*- coding:utf8 -*- import os import sys import math def halfSearch(arr=[1,2,3,4,5],find = 5): ''' Binary search, 2 finding Binary search is data are ordered Algorithm :mid = Math.floor(low+hight/2) ''' low = 0 high = len(arr) while(True): mid = (l

  • Data Structure Review (2) binary search algorithm 2010-07-27

    package algorithm.search; public class Search { public int BinSearch(int [] a,int k){ int low = 0; int high = a.length-1; while(low<=high){ int mid = (low+high+1)/2; if(k==a[mid]){ return mid; }else if(k<a[mid]){ high = mid-1; }else{ low = mid+1; }

  • [Transfer] heuristic search algorithm Introduction ------ A * algorithm theory and practice 2010-12-14

    Introduction to Heuristics Search ------ A * Algorithm Principle and Practice [Classify] Algorithm Implementation, Artificial Intelligence [Level] ★ ★ ★ ★ ★ [Abstract] This article introduces an important and effective heuristics algorithm ------ A *

  • Google Panda comprehensive on-line search algorithm 2011-08-15

    Google announced for the "contents of the farm" spam sites Panda algorithm has been a comprehensive global on-line, all languages ​​have already deployed the Google search algorithms on the Panda, in addition to Japanese, Korean and Chinese as t

  • PHP binary search algorithm and a detailed analysis of the sample 2010-08-30

    Write himself a binary search function is php achieved. I think many people in the interview, they also encountered this problem. Well, crap too much, go! /** * Two algorithms to find * @param array $array To find an array of * @param int $min_key Th

  • University Notes - binary search algorithm 2010-10-02

    Thought: The N elements are divided into roughly the same number of two and a half, take the middle of a [n / 2], if x = a [n / 2], is to find x, the algorithm terminates, if x <a [n / 2 ], then a [n] to find the left half of x, if x> a [n / 2], in

  • Only 10% of programmers can correctly implement binary search algorithm 2010-11-30

    / / Copyright 2009 Nicholas C. Zakas. All rights reserved. / / MIT-Licensed, see source file function binarySearch (items, value) { var startIndex = 0, stopIndex = items.length - 1, middle = Math.floor ((stopIndex + startIndex) / 2); while (items [mi

  • Linux kernel in the BM string search algorithm, a small BUG 2011-01-10

    Copyleft this document owned by yfydz all, the use of GPL, free to copy, reprint, reproduced keep the documents for completeness, Used for any commercial purposes is strictly prohibited. msn: [email protected] Source: http://yfydz.cublog.cn In th