2018-07-27 二分查找法

二分查找是一种查询效率非常高的查找算法。又称折半查找。
二分查找的前提必须是有序的序列，优点是查询速度快，缺点是必须是有序序列
有序的序列，每次都是以序列的中间位置的数来与待查找的关键字进行比较，每次缩小一半的查找范围，直到匹配成功。

画图分析：

思路:
A：定义最小索引，最大索引
B：计算出中间索引
C：拿中间索引值和要查找的值作比较，
---- 相等：则直接返回
---- 大于：在右边找
---- 小于：在左边找

实现代码如下：

/**
 * 二分查找
 *
 */
public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {0,11,22,33,44,55,66,77,88};
        
        System.out.println("66的索引位置:" + BinarySearch.binarySearch(arr, 88));
        System.out.println("33的索引位置:" + BinarySearch.binarySearch(arr, 33));
        System.out.println("100的索引位置:" + BinarySearch.binarySearch(arr, 100));
        System.out.println("-----------------------------------");
        System.out.println("66的索引位置:" + BinarySearch.binarySearch2(arr, 66));
        System.out.println("33的索引位置:" + BinarySearch.binarySearch2(arr, 0));
        System.out.println("100的索引位置:" + BinarySearch.binarySearch2(arr, 100));
        System.out.println("-----------------------------------");
        System.out.println("66的索引位置:" + BinarySearch.binarySearch3(arr, 66, 0, arr.length-1));
        System.out.println("33的索引位置:" + BinarySearch.binarySearch3(arr, 33, 0, arr.length-1));
        System.out.println("100的索引位置:" + BinarySearch.binarySearch3(arr, 100, 0, arr.length-1));
    }
    
    // 方式1
    public static int binarySearch(int[] arr, int value) {
        int min = 0;
        int max = arr.length - 1;
        int mid = (min + max) / 2;
        
        while (arr[mid] != value) {
            if (arr[mid] > value) {
                max = mid - 1;
            } else if (arr[mid] < value) {
                min = mid + 1;
            }
            if (min > max) {
                return -1;
            }
            mid = (min + max) / 2;
        }
        return mid;
    }
    
    // 方式2
    public static int binarySearch2(int[] arr, int value) {
        int min = 0;
        int max = arr.length - 1;
        int mid = (min + max) / 2;
        
        while (min <= max) {
            if (arr[mid] == value) {
                return mid;
            }
            if (arr[mid] > value) {
                max = mid - 1;
            } else if (arr[mid] < value) {
                min = mid + 1;
            }
            
            mid = (min + max) / 2;
        }
        return -1;
    }
    
    // 方式3 递归查找
    public static int binarySearch3(int[] arr, int value, int min, int max) {
        if (min > max) {
            return -1;
        }
        int mid = (min + max) / 2;
        if (arr[mid] > value) {
            return binarySearch3(arr, value, min, mid-1);
        } else if (arr[mid] < value) {
            return binarySearch3(arr, value, mid+1, max);
        }
        return mid;
    }
}

运行结果:

66的索引位置:8
33的索引位置:3
100的索引位置:-1
-----------------------------------
66的索引位置:6
33的索引位置:0
100的索引位置:-1
-----------------------------------
66的索引位置:6
33的索引位置:3
100的索引位置:-1

前两种方式差不多，都是通过循环。
第三种方式是通过递归，递归相对来说要占内存，推荐使用前两种方式。