package algorithm;
//线性查找法也不是一无是处，它最大的优点就是简单，特别简单，傻瓜式的
//二分法本身也有局限性，那就是二分法必须要求待查数组是已排序的，比如我给你一个很大的数组，
//但是这个数组并没有排序，那你如果想用二分查找法的话还必须先给数组排序，然后再查找。
//这样就会造成除查找之外的额外成本（排序）
public class searchDemo {
    public static void main(String[] args) {
        int[] data = {2, 1, 4, 6, 12, 7};
        int target = 2;
        int searchIndex = search(data, target);
        int index = binarySearch2(data, 0, data.length - 1, target);
        if (searchIndex != -1) {
            System.out.println("found at: " + searchIndex);
            System.out.println("found ：" + index);
        }else {
            System.out.println("not found");
        }
    }
    /*
    *@param  data   待查找的数组
    *@param  target 待查找的值
    *@return int    目标值在数组中的索引，如果没找到返回-1 
    */
    public static int search(int[] data, int target) {

        int length = data.length;

        //从头遍历数组中的各个值，如果找到目标值就返回其索引
        for (int i = 0; i < length; i++) {
            if (data[i] == target) {
                return i;
            }
        }

        //代码能走到这一步就说明上面的循环遍历结束了也没找到目标值
        //即目标值不存在于数组中
        return -1;

    }
    /** 
     * 递归方法实现二分查找
     * @param data   已排序数组(这里假设是从小到大排序) 
     * @param from   起始位置 
     * @param to     终止位置 
     * @param target 要查找的值
     * @return 要查找的值在数组中的位置，如果没找到则返回-1
     */  
    private static int binarySearch1(int[] data, int from, int to, int target) {
        if (from <= to) {
            int mid = from + (to - from) / 2;//中间位置，为了防止溢出使用这种方式求中间位置
            if (data[mid] < target) {//中间的值比目标值小，则在左半边继续查找
                return binarySearch1(data, mid + 1, to, target);
            }else if(data[mid] > target){//中间的值比目标值大，则在右半边继续查找
                return binarySearch1(data, from, mid - 1, target);    
            }else {//找到了，把找到的情况放在最后是因为多数情况下中间值不是大于就是小于，这样做可以节省操作
                return mid;
            }
        }
        return -1;
    }

    /** 
     * 非递归方法实现二分查找
     * @param data   已排序数组(这里假设是从小到大排序) 
     * @param from   起始位置 
     * @param to     终止位置 
     * @param target 要查找的值
     * @return 要查找的值在数组中的位置，如果没找到则返回-1
     */  
    private static int binarySearch2(int[] data, int from, int to, int target) {
        while(from <= to) {
            int mid = from + (to - from) / 2;
            if (data[mid] < target) {
                from = mid + 1;                
            }else if(data[mid] > target) {
                to = mid - 1;
            }else {//找到了，把找到的情况放在最后是因为多数情况下中间值不是大于就是小于，这样做可以节省操作
                return mid;
            }
        }
        return -1;
    }




}