关于二分查找及变体

关于二分查找及变体

/********************************************
 * All Rights Reserved By www.laughing.ren
 * @author:Laughing_Lz
 * @version:2018年11月22日 下午11:28:28
 * ******************************************/
package ren.laughing.code.Test;

import java.util.Arrays;

public class Search {

    /**
     * 简单的二分查找,前提是数组是有序,且无重复值
     * 
     * @param arr arr
     */
    public static int binarySearch(int valueint[] arr{
        int low = 0, high = arr.length - 1, middle;
        // 为什么要是<=呢?
        while (low <= high) {
            middle = low + ((high - low) >> 1);
            if (arr[middle] < value) {
                low = middle + 1;
            } else if (arr[middle] > value) {
                high = middle - 1;
            } else {
                return middle;
            }
        }
        return -1;

    }

    /**
     * 递归方法实现简单二分查找,前提同上:数组有序,且无重复值
     * 
     * @param value value
     * @param arr   arr
     * @param low   low
     * @param high  high
     * @return
     */
    public static int recursionBinarySearch(int valueint[] arr, int low, int high{
        if (low > high) {
            return -1;
        }
        int middle = low + ((high - low) >> 1);
        if (arr[middle] == value) {
            return middle;
        } else if (arr[middle] > value) {
            return recursionBinarySearch(value, arr, low, middle - 1);
        } else {
            return recursionBinarySearch(value, arr, middle + 1, high);
        }

    }

    /**
     * 求解一个数的平方根,精确到小数六位
     * 
     * @param n n
     * @return
     */
    public static float square(float n{
        if (n == 0 || n == 1) {
            return 1;
        }
        float low = 0, high = n;
        float middle = low + (high - low) / 2;
        while (Math.abs(middle * middle - n) > 0.000001) {
            if (middle * middle > n) {
                high = middle;
            } else if (middle * middle < n) {
                low = middle;
            } else {
                return middle;
            }
            middle = low + (high - low) / 2;
        }
        return middle;
    }

    /**
     * 利用二分查找返回数组中第一个出现value的位置,注意边界条件middle==0
     * 
     * @param arr   arr
     * @param value value
     * @return
     */
    public static int firstEqual(int[] arr, int value{
        int low = 0, high = arr.length - 1, middle = low + ((high - low) >> 1);
        while (low <= high) {
            if (arr[middle] > value) {
                high = middle - 1;
            } else if (arr[middle] < value) {
                low = middle + 1;
            } else {
                if ((middle == 0) || (arr[middle - 1] < value)) {
                    return middle;
                } else {
                    high = middle - 1;
                }
            }
            middle = low + ((high - low) >> 1);
        }
        return -1;
    }

    /**
     * 利用二分查找返回数组中最后一个出现value的位置
     * 
     * @param arr   arr
     * @param value value
     * @return
     */
    public static int lastEqual(int[] arr, int value{
        int low = 0, high = arr.length - 1, middle = low + ((high - low) >> 1);
        while (low < high) {
            if (arr[middle] > value) {
                high = middle - 1;
            } else if (arr[middle] < value) {
                low = middle + 1;
            } else {
                if ((middle == arr.length - 1) || (arr[middle + 1] > value)) {
                    return middle;
                } else {
                    low = middle + 1;
                }
            }
            middle = low + ((high - low) >> 1);
        }
        return -1;

    }

    /**
     * 利用二分查找返回数组中第一个大于value的位置
     * 
     * @param arr   arr
     * @param value value
     * @return
     */
    public static int firstGreat(int[] arr, int value{
        int low = 0, high = arr.length - 1, middle = low + ((high - low) >> 1);
        while (low <= high) {
            if (arr[middle] > value && arr[middle - 1] <= value) {
                return middle;
            } else if (arr[middle] <= value) {
                low = middle + 1;
            } else {
                high = middle - 1;
            }
            middle = low + ((high - low) >> 1);
        }
        return -1;
    }

    /**
     * 利用二分查找返回数组中最后一个小于value的位置
     * 
     * @param arr   arr
     * @param value value
     * @return
     */
    public static int lastLess(int[] arr, int value{
        int low = 0, high = arr.length - 1, middle = low + ((high - low) >> 1);
        while (low <= high) {
            if (arr[middle] < value && arr[middle + 1] >= value) {
                return middle;
            } else if (arr[middle] >= value) {
                high = middle - 1;
            } else {
                low = middle + 1;
            }
            middle = low + ((high - low) >> 1);
        }
        return -1;
    }

    /**
     * 循环数组中使用二分查找获取value所在位置
     * 
     * @param arr   arr
     * @param value value
     * @return
     */
    public static int loopBinarySearch(int[] arr, int value{
        if(arr.length < 1) {
            return -1;
        }
        if (arr.length == 1) {
            if (arr[0] == value) {
                return 0;
            } else {
                return -1;
            }
        }
        int low = 0, high = arr.length, middle = 0;
        // 首先获取首末位置
        for (int i = 0; i < arr.length - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                high = i;
                low = i + 1;
            }
        }
        if (arr[arr.length - 1] > arr[0]) {
            low = 0;
            high = arr.length - 1;
        }
        // 经过和arr[0]判断后筛选出可能包含value的子数组
        if (arr[0] == value) {
            return 0;
        } else if (arr[0] < value) {
            low = 1;
        } else if (arr[0] > value) {
            high = arr.length - 1;
        }
        // 使用简单二分查找获取value位置
        while (low <= high) {
            middle = low + ((high - low) >> 1);
            if (arr[middle] > value) {
                high = middle - 1;
            } else if (arr[middle] < value) {
                low = middle + 1;
            } else {
                return middle;
            }
        }
        return -1;
    }

    public static void main(String[] args{
        int[] arr = { 2146730985 };
        Arrays.sort(arr);
//        System.out.println(binarySearch(5, arr));
//        System.out.println(recursionBinarySearch(5, arr, 0, arr.length - 1));
        System.out.println(square(5f));
        int[] arr1 = { 01234455589 };
        System.out.println(firstEqual(arr1, 5));
        System.out.println(lastEqual(arr1, 5));
        System.out.println(firstGreat(arr1, 5));
        System.out.println(lastLess(arr1, 5));
        int[] arr2 = { 7890123456 };
        System.out.println(loopBinarySearch(arr2, 8));

    }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注