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.