二分查找：时间复杂度O(logn)，但必须是sorted的数组。二分查找最差情况是not found。
线性查找：时间复杂度O(n)
// 通用二分查找 public class BinarySearch { public static void main(String[] args) { int[] a = {1, 2, 3}; System.out.println(binarySearch(a, 2)); } static int binarySearch(int[] A, int target) { if (A.length == 0) { return -1; } int start = 0; int end = A.length - 1; //注意-1 int mid; while (start + 1 < end) { //注意是+1 mid = start + (end - start) / 2; if (A[mid] == target) { end = mid; //如果不找第一个，可以直接返回。 } else if (A[mid] < target){ start = mid; } else { end = mid; } } //注意输出 if (A[start] == target) { return start; } if (A[end] == target) { return end; } return -1; } }/**
public class BinarySearch { public static void main(String[] args) { } /** * 非递归 */ public static int binarySearch(int[]data, int key) { int low = 0; int high = data.length - 1; while (low <= high) {//注意有等于号 int mid = low + ((high - low) >> 1); //不能直接用(high + low) /2 ,易超过int的范围 if (key == data[mid]) { return mid; } else if (key < data[mid]) { high = mid - 1; } else { low = mid + 1; } } return -1; } /** * 递归 */ public static int binarySearch(int Array[], int low, int high, int key) { if (low <= high) { int mid = low + ((high - low) >> 1); if(key == Array[mid]) { return mid; } else if (key < Array[mid]) { return binarySearch(Array, low, mid - 1, key); } else { return binarySearch(Array, mid + 1, high, key); } } else { return -1; } } }
