前提知识:

　　

普通查询:本质通过数组的遍历与if逻辑结构判断实现

　　实现步骤:

　　　　1. 遍历数组

　　　　2. 遍历过程中,使用元素和数组中的元素进行比较

　　　　　　如果相同,返回元素在数组中的索引

　　　　　　如果不同,返回负数

public static int search(int[] arr, int key){　　//遍历数组　　for(int i = 0 ; i < arr.length ; i++){　　　　//数组元素,被查找的元素比较　　　　if(arr[i] == key){　　　　　　//返回索引　　　　　　return i;　　　　}　　}　　return -1;}

折半查找:前提数组必须为从小到大不重复线性数组!

 

非递归方式:

public static int binarySearch(int[] arr, int key){         //定义三个指针变量 存储 左区间索引 中间索引 右区间索引         int min = 0 ;         int max = arr.length -1 ;         int mid = 0;         //循环折半,条件 min<=max         while( min <= max){             //公式,计算中间索引                    mid = (min+max)/2;             if(key > arr[mid]){                 min = mid + 1;             }else if (key < arr[mid]){                 //元素 < 中间索引  大指针= 中间-1                 max = mid - 1;             }else{                 //元素 == 中间索引  找到了,结束了,返回中间索引                        return mid;             }         }         //循环结束,无法折半,元素没有找到 ,返回-1         return -1;}

JDK1.8的java.utils.Arrays的二分查询底层源码分析

// Like public version, but without range checks.    private static int binarySearch0(int[] a, int fromIndex, int toIndex,int key) {        int low = fromIndex;        int high = toIndex - 1; 　　　　//循环折半判断        while (low <= high) {
    　　　　　　//位运算 >>>1 右移一位等效与 /2            int mid = (low + high) >>> 1;            int midVal = a[mid];            if (midVal < key)                low = mid + 1;            else if (midVal > key)                high = mid - 1;            else                return mid; // key found        }        return -(low + 1);  // key not found.    }

 

递归方式:

int  binarySearch(int[] arr ,int start ,int end,int key){    int mid = (start+end)/2; 　　//递归出口1: 左区间索引比右区间索引大    if(start>end){        return -1;    } 　　//递归出口2:找到对应key值得索引    if(key == arr[mid]){        return mid;    }else if (key > arr[mid]) {        return binarySearch(arr, mid + 1, end, key);    } else {
   //if (key < arr[mid]) {
           return  binarySearch(arr, start, mid - 1, key);　}}