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

简介

二分查找又称折半查找、二分搜索、折半搜索等，是在分治算法基础上演变的查找算法

二分查找算法仅适用于有序序列，它只能用在升序序列或者降序序列中查找目标元素

二分查找局限性

依赖数组结构

二分查找需要利用下标随机访问元素，如果使用链表等其他数据结构则无法实现二分查找

针对有序的数据

二分查找需要的数据必须是有序的。如果数据没有序，需要先排序，排序的时间复杂度最低是 O(nlogn)。所以，如果针对的是一组静态的数据，没有频繁地插入、删除，可以进行一次排序，多次二分查找

如果数据集合有频繁的插入和删除操作，要想用二分查找，要么每次插入、删除操作之后保证数据仍然有序，要么在每次二分查找之前都先进行排序。针对这种动态数据集合，无论哪种方法，维护有序的成本都是很高的

二分查找只能用在插入、删除操作不频繁，一次排序多次查找的场景中。针对动态变化的数据集合，二分查找将不再适用

数据量大小

• 数据量太小不适合二分查找

  如果要处理的数据量很小，完全没有必要用二分查找，顺序遍历就足够了

• 数据量太大不适合二分查找

  二分查找底层依赖的是数组，数组需要的是一段连续的存储空间，所以数据比较大时，比如1GB，这时候可能不太适合使用二分查找，因为内存都是离散的，可能电脑没有这么多的内存

算法图解

从图中可以看出，每次查找目标值时都需要将目标值跟中间值进行比较，以判断出目标值在中间值的左边还是右边亦或是目标值就是中间值

中间值得计算有两种方式：

right 表示搜索区域内最后一个元素所在位置，left 表示搜索区域内第一个元素所在的位置，mid 表示中间元素所在的位置

• 方法一：mid = ( left + right) / 2
  • 该方法存在溢出的风险，当 left 和 right 比较大时，有可能会导致 mid 的值错误，从而使程序出错
• 方法二：mid = left + (right – left) / 2
  • 该方法则可以保证生成的 mid 一定大于 left，小于 right

代码实现

循环方法

/**
 * 二分查找--循环方法
 * @param arr       原数组
 * @param left      左指针
 * @param right     右指针
 * @param target    目标值
 * @return          寻找目标值第一次出现的下标值，不存在则返回-1
 */
public int binarySearch(int[] arr,int left,int right,int target){

    int mid = left + (right - left) / 2;
    while (left < right) {
        if (target > arr[mid]) {
            //目标值位于中间值的右边
            left = mid + 1;
        } else if (target < arr[mid]){
            //目标值位于中间值的左边
            right = mid - 1;
        } else if (target == arr[mid]){
            //找到目标值下标
            return mid;
        }

        //找出中间值下标
        mid = left + (right - left) / 2;
    }

    //找不到
    return -1;
}

递归方式

/**
 * 二分查找--递归方式
 * @param arr       原数组
 * @param left      左指针
 * @param right     右指针
 * @param target    目标值
 * @return  寻找目标值第一次出现的下标值，不存在则返回-1
 */
public int binarySearch(int[] arr,int left,int right,int target){

    //没有在数组中找到目标值
    if (left > right) {
        return -1;
    }

    //获取该次查找目标值的数组中间值下标
    int mid = left + (right - left) / 2;

    if (target > arr[mid]){
        //目标值大于中间值，则目标值在中间值的右边
        return binarySearch(arr,mid + 1,right,target);
    } else if (target < arr[mid]){
        //目标值小于中间值，则目标值在中间值的左边
        return binarySearch(arr,left,mid - 1,target);
    } else {
        //查到目标值第一次出现的下标值
        return mid;
    }
}