数据结构与算法之二分查找

   二分查找又称折半查找、二分搜索，是一种在有序数组中查找某一特定元素的搜索算法，这种算法建立在有序数组的基础上；

实现思路：

   ①  找出位于数组中间的值，并存放在一个变量temp中
   ②  将需要找到的key和temp比较
    ????  如果key大于temp,则把数组中间位置作为下一次计算的起点，并重复①和②
   ④  如果key小于temp,则把数组中间位置作为下一次计算的终点，并重复①、②和????
   ????  如果key等于temp,则停止查找，返回数组下标,如果不存在则返回-1

      时间复杂度O(log2n) 空间复杂度O(1)

public class binarySearch {

    /**
     * 使用递归方式实现二分查找
     * @param arr 需要查找的有序数组
     * @param from 起始下标
     * @param to 终止下标
     * @param key 需要查找的关键字
     * @throws Exception
     */
    public static  int search(int[] arr , int from , int to , int key) throws Exception
    {
        if (from < 0 || to < 0)
        {
            throw new IllegalArgumentException("数组长度需要大于0");
        }
        if (from <= to)
        {
            int middle = (from >>> 1) + (to >>> 1);//右移即除二，等同于 (from+to)/2
            int temp = arr[middle];
            if (key > temp)
            {
                from = middle + 1;
            }
            else if (key < temp)
            {
                to = middle - 1;
            } else {
                return middle;
            }
        }
        return search(arr, from, to, key);
    }

    public static void main(String[] args) throws Exception{

         int[] arr = {2, 5, 7, 9, 13};

         int ss = search(arr, 0, 4, 13);

         System.out.println("查找到数字的下标是" + ss);
    }

}