package part1;

/**

 * Created by Administrator on 2018/7/31.

 */

public class demo01{

    /*

    * 循环实现二分查找算法arr 已排好序的数组x 需要查找的数-1 无法查到数据

    */

    /**

     *

     * @param arr  数组对象

     * @param x    所要查找的数

     * @return

     */

    public static int binarySearch(int[] arr, int x) {

        int low = 0;

        int high = arr.length-1;

        while(low <= high) {

            int middle = (low + high)/2;  //取中间索引

            if(x == arr[middle]) {

                return middle;

            }else if(x <arr[middle]) {

                high = middle - 1;       //如果所找的的数小于中间索引对应的值证明所要找的数在左半边,将中间索引前一位设置为终点索引

            }else {

                low = middle + 1;         //如果所找的的数大于中间索引对应的值证明所要找的数在右半边,将中间索引后一位设置为开始索引

            }

        }

        return -1;

    }

    //递归实现二分查找

    /**

     *

     * @param dataset   数组对象

     * @param data       所要查找的数

     * @param beginIndex  开始索引

     * @param endIndex    结束索引

     * @return

     */

    public static int binarySearch(int[] dataset,int data,int beginIndex,int endIndex){

        int midIndex = (beginIndex+endIndex)/2;  //取中间索引

        //如果查找的数小于第一位数  或者  查找的数大于最后一位数  或者  起始索引大于结束索引 都说明所查找的数不存在

        if(data <dataset[beginIndex]||data>dataset[endIndex]||beginIndex>endIndex){

            return -1;

        }

        //如果查找的数小于中间索引对应的值说明找的数在左半边，递归调用该查找方法，结束索引为中间索引向左移动一位

        if(data <dataset[midIndex]){

            return binarySearch(dataset,data,beginIndex,midIndex-1);

        //如果查找的数大于于中间索引对应的值说明找的数在右半边，递归调用该查找方法，起始索引为中间索引向右移动一位

        }else if(data>dataset[midIndex]){

            return binarySearch(dataset,data,midIndex+1,endIndex);

        //如果所查找的数正好等于中间索引对应的值，那么就将该索引返回

        }else {

            return midIndex;

        }

    }

    public static void main(String[] args) {

        int[] arr = { 11,22,33,44,55,66,77,88};

       System.out.println("循环查找：" + (binarySearch(arr, 44) + 1));

        System.out.println("递归查找"+(binarySearch(arr,44,0,arr.length-1)+1));

    }

}