数据结构与算法学习-二分查找及其变形

二分查找

1、二分查找针对的是一个有序集合，查找思想主要采用分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素。要查找的元素比中间的元素小，则将范围缩小为集合的前半部分，如果待查找的元素比中间的元素大，则将将范围缩小为集合的后半部分，然后重复这个过程，直到找到元素的下标为止。

2、二分查找的时间复杂度：O(logn)

3、二分查找的局限性：

(1)二分查找依赖的是顺序表结构，简单点说就是数组

(2)二分查找针对的是有序数据,也就是说集合排好序后，才能使用二分查找

(3)数据量太小不适合二分查找，数量小的话，直接遍历就可以，可不用二分查找。

(4)数据量太大也不适合二分查找，由于依赖于顺序表结构，这里以数组为例，数组在存储结构上是逻辑连续的，数据量很大，意味着需要申请很大的连续的内存空间，这就导致很大的局限性。

代码实现

public class BinarySearch {

    /**
     * 二分查找迭代算法
     *
     * @param arr   数组
     * @param len   长度
     * @param value 要找的值
     * @return
     */
    public static int binarySearch(int[] arr, int len, int value) {
        if (arr == null) {
            return -1;
        }
        int low = 0;
        int high = len - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (arr[mid] > value) {
                high = mid - 1;
            } else if (arr[mid] < value) {
                low = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

    /**
     * 二分查找-递归
     *
     * @param arr   数组
     * @param len   长度
     * @param value 要找的值
     * @return
     */
    public static int binarySearchRecursion(int[] arr, int len, int value) {
        if (arr == null) {
            return -1;
        }
        return bsBinarySearch(arr, 0, len - 1, value);
    }

    public static int bsBinarySearch(int[] arr, int low, int high, int value) {
        if (low > high) {
            return -1;
        }
        int mid = (low + high) >> 1;
        if (arr[mid] > value) {
            return bsBinarySearch(arr, low, mid - 1, value);
        } else if (arr[mid] < value) {
            return bsBinarySearch(arr, mid + 1, high, value);
        } else {
            return mid;
        }
    }

    /**
     * 变体一：查找第一个值等于给定值的元素
     */
    public static int binarySearch1(int[] arr, int len, int value) {
        if (arr == null) {
            return -1;
        }
        int low = 0;
        int high = len - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (arr[mid] > value) {
                high = mid - 1;
            } else if (arr[mid] < value) {
                low = mid + 1;
            } else {
                if (mid == 0 || arr[mid - 1] != value) {
                    return mid;
                } else {
                    high = mid - 1;
                }
            }
        }
        return -1;
    }

    /**
     * 变体二：查找最后一个值等于给定值的元素
     */
    public static int binarySearch2(int[] arr, int len, int value) {
        if (arr == null) {
            return -1;
        }
        int low = 0;
        int high = len - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (arr[mid] > value) {
                high = mid - 1;
            } else if (arr[mid] < value) {
                low = mid + 1;
            } else {
                if (mid == len - 1 || arr[mid + 1] != value) {
                    return mid;
                } else {
                    low = mid + 1;
                }
            }
        }
        return -1;
    }

    /**
     * 变体三：查找第一个大于等于给定值的元素
     */
    public static int binarySearch3(int[] arr, int len, int value) {
        if (arr == null) {
            return -1;
        }
        int low = 0;
        int high = len - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (arr[mid] >= value) {
                if (mid == 0 || arr[mid - 1] < value) {
                    return mid;
                } else {
                    high = mid - 1;
                }
            } else {
                low = mid + 1;
            }
        }
        return -1;
    }

    /**
     * 变体四：查找最后一个小于等于给定值的元素
     */
    public static int binarySearch4(int[] arr, int len, int value) {
        if (arr == null) {
            return -1;
        }
        int low = 0;
        int high = len - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (arr[mid] > value) {
                high = mid - 1;
            } else {
                if (mid == len - 1 || arr[mid + 1] > value) {
                    return mid;
                } else {
                    low = mid + 1;
                }
            }
        }
        return -1;
    }
}

代码地址

二分查找