二分法在有序序列中查找某个数值是java中的经典算法，它能在大量的数据中找到自己想找的元素，减少查找的循环的次数。使用二分法的前提是待查找的序列必须是有序的，如果不是可以先转换为有序序列。通过将有序序列一分为二的方法，不断逼近目标值。

1、二分法介绍

二分法的用途：能在大量的数据中找到自己想找的元素，减少查找的循环的次数。

二分法的条件：必须是一个有序的序列，才能使用二分法。对于非有序序列，可以先进行排序后再使用二分法查找。

二分法的原理：对一个有序数列进行查找的时候，利用中间值来一步步缩小搜索的范围，直至找到最终结果。时间复杂度：O(log(n))。

二分法使用方法：

1. 将长度为n的数组进行排序，升降序都可以。
2. 先把数组的范围标记好，分别用low和high来表示数组的范围，然后找到数组的中间元素 mid=（low+high）/2
3. 使用 mid 位置的元素和所查找的元素 key 进行对比，如果 key 的数值较为大的话，就进入（mid，high）的范围在进行查找元素，如果 key 的元素较为小的话就进入（low，mid）的范围查找。
4. 循环这个步骤，这时我们只需要根据key，与数组的最中间的值进行比较，根据结果改变low，high的值就好了。直到找到对应的值或者区间缩小到左右端点之间不再包含其他数据结束。

2、问题及实现方式

2.1 问题

有一个无重复数字的数组中，利用二分法查找某个数字在数组中的位置，找到则返回其位置号，没找到返回-1.

2.2 实现方式

2.2.1 递归算法

package com.kz.example.algorithm.find;

import java.util.Arrays;

/**
 * 二分法查找
 * 
 * 假设数据是按升序排序的，对于给定值key，从序列的中间位置mid开始比较，如果当前位置array[mid]值等于value，则查找成功；
 * 若value小于当前位置值array[mid]，则在数列的前半段中查找,array[low,mid-1]；
 * 若value大于当前位置值array[mid]，则在数列的后半段中继续查找array[mid+1,high]，直到找到为止,时间复杂度:O(log(n))
 */
public class BinarySearch {

    public static void main(String[] args) {
        int array[] = {11, 23, 54, 65, 76, 13, 55, 66, 70, 98, 30, 99, 103};
        // 将数组排序
        Arrays.sort(array);
        System.out.println(Arrays.toString(array));
        // 查找元素55的位置
        System.out.println(recurBinarySearch(array, 55, 0, array.length - 1));
    }

    /**
     * 二分法查找元素的位置 递归算法，需要传递数组的头和尾的位置。
     *
     * @param array 数组
     * @param value 需要查找的值
     * @param low 查找的头部位置
     * @param high 查找的尾部位置
     * @return
     */
    public static int recurBinarySearch(int array[], int value, int low, int high) {
        int mid;
        mid = (low + high) / 2;
        if (low > high) {
            return -1;
        }
        if (array[mid] == value) {
            return mid;
        } else if (array[mid] > value) {
            return recurBinarySearch(array, value, low, mid - 1);
        } else {
            return recurBinarySearch(array, value, mid + 1, high);
        }

    }

}

2.2.2 非递归算法（循环）

package com.kz.example.algorithm.find;

import java.util.Arrays;

/**
 * 二分法查找
 * 基本思想：
 * 假设数据是按升序排序的，对于给定值key，从序列的中间位置mid开始比较，如果当前位置array[mid]值等于value，则查找成功；
 * 若value小于当前位置值array[mid]，则在数列的前半段中查找,array[low,mid-1]；
 * 若value大于当前位置值array[mid]，则在数列的后半段中继续查找array[mid+1,high]，直到找到为止,时间复杂度:O(log(n))
 */
public class BinarySearch {
    
    public static void main(String[] args) {
        int array[] = {11, 23, 54, 65, 76, 13, 55, 66, 70, 98, 30, 99, 103};
        // 将数组排序
        Arrays.sort(array);
        System.out.println(Arrays.toString(array));
        /* 查找元素76的位置(非递归算法) */
        System.out.println(binarySearch(array, 76));
    }

    /**
     * 二分法查找元素的位置 非递归算法
     *
     * @param array
     * @param value
     * @return
     */
    public static int binarySearch(int array[], int value) {
        int low = 0;
        int high = array.length - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (array[mid] == value) {
                return mid;
            }
            if (array[mid] > value) {
                high = mid - 1;
            }
            if (array[mid] < value) {
                low = mid + 1;
            }
        }
        return -1;
    }
}