数据结构与算法-二分查找(一)

用户3470542

发布于 2019-06-26 16:22:56

7050

发布于 2019-06-26 16:22:56

二分查找理解

二分查找也称为折半查找，主要用在有序集合中进行查找。我们先通过一个猜数字的小游戏来分析。首先我随机写一个0~99的数字，然后你再猜我写的哪一个数字，在猜数字过程中如果你猜大了，我会提示你猜的数字大于我写的数字；如果你猜小了，我会提示你猜的数字小于我写的数字，直到猜中为止。那么如何快速猜中呢？

这里就可以用到二分查找的思想了，假设我写下的数字为16，那么可以通过如下步骤进行猜测：

通过很少的次数（6次）就可以猜到数字。

为了方便用图形表示，我们假设在11~20之间找到16，如下图所示为查找过程，其中 low和 high表示待查找区间的下标， mid表示待查找区间的中间元素下标。

二分查找是针对的一个有序的数据结合，查找思想有点类似分治思想，每次通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为0。

二分查找的效率是非常高的，时间复杂度为 O(logn)。

二分查找代码实现

这里讨论的是在有序数组中不存在重复元素的二分查找代码实现，我们实现递归版本与非递归版。

非递归版本

public int binarySearch(int[] nums, int n, int val){    int low = 0;        // low表示待查找区间的起始位置的下标    int high = n - 1;   // high表示待查找区间的终止位置的下标
    while(low <= high){        int mid = low + (high - low) / 2;   // mid表示待查找区间的中间位置的下标        if (nums[mid] < val){               // 如上图第2步情况            low = mid+1;        }else if(nums[mid] > val){          // 如上图第3步情况            high = mid - 1;        }else{                              // 当找到该数时，直接返回mid即可            return mid;        }    }
    return -1;  // 当数字中没有需要查找的数，返回-1.}

这里需要注意如下几点：

循环退出条件为： low<=high而不是 low<high
mid的取值：不能将 mid写成 mid=(low+high)/2。因为如果在 int类型情况下，当 low和 high之和大于 int类型的最大值，就会溢出，导致结果错误。因此需要写成 mid=low+(high-low)/2。更进一步，如果要将性能优化到极致，可以使用位运算进行计算， mid=low+((high-low)>>1)。

递归版本

public int binarySearch(int[] nums, int n, int val){    return help(nums, 0, n-1, val);}
/** * 辅助函数 * @param nums 数组 * @param low 待查找区间的起始位置的下标 * @param high 待查找区间的终止位置的下标 * @param val 待查找的值 * @return 查找到的值的下标，如果没有这个数，则返回-1 */private int help(int[] nums, int low, int high, int val) {    // 当数字中没有需要查找的数，返回-1    if(low > high)        return -1;
    int mid = low + (high - low) / 2;   // mid表示待查找区间的中间位置的下标
    if (nums[mid] < val){               // 如上图第2步情况        return help(nums, mid+1, high, val);    }else if(nums[mid] > val){          // 如上图第3步情况        return help(nums, low, mid-1, val);    }else{                              // 当找到该数时，直接返回mid即可        return mid;    }}

二分查找应用场景的局限性

二分查找有着查找效率高的优点，但是并不是所有的情况都可以进行二分查找。

二分查找依赖的是顺序表结构，一般是以数组的形式使用，因为二分查找需要按照下标随机访问，因此对于链表结构不能使用二分查找。
二分查找针对的是有序数据。对于在没有序的情况下，需要对数据进行排序。如果对一组数据没有频繁的插入删除操作，我们可以通过一次排序后进行多次二分查找，这时的成本是比较可观的。但是对于数据需要多次的插入删除操作，我们使用二分查找前需要对这组数据进行排序，这时维护数组有序的成本比较高，这时就不适合使用二分查找。
数据量太小不适合二分查找。如果数据量太小时，我们可以通过一次遍历即可查找，而不需要使用二分查找，只有当数据量较大的时候二分查找的优势才能体现出来。
数据量特别大时也不适合二分查找。因为二分查找需要依赖数组，在申请数组时对内存空间要求比较苛刻。如我们有1GB的数据，使用二分查找的时就需要连续的1GB的内存空间。

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2019-06-15，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自算法半岛微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度