龙空技术网

一文搞懂二分查找算法

南秋同学 83

前言:

现时我们对“高效查找算法是什么”大概比较注重,同学们都想要知道一些“高效查找算法是什么”的相关内容。那么小编同时在网络上收集了一些关于“高效查找算法是什么””的相关文章,希望同学们能喜欢,同学们快快来了解一下吧!

二分查找

二分查找针对的是一个有序的数据集合,查找思想有点类似分治思想,每次通过与区间的中间元素比较,将待查找的区间缩小为原来的一半,直到找到要查找的元素或区间缩小到0。

二分查找是一种非常高效的查找算法,假设数据大小为n,每次查找后数据都会缩小为原来的一半。最坏情况下,直到查找区间被缩小为空才停止。

如图所示:

可以看出,以上展示的是一个等比数列。其中n/2^k=1时,k值表示缩小的总次数,每一次缩小操作只涉及两个数据的大小比较,经过k次区间缩小操作,时间复杂度为O(k)。通过n/2^k=1可以求得k=log2^n,因此,二分查找算法的时间复杂度为O(logn)。

二分查找模板

二分查找基本模板:

public int binarySearch(int[] nums, int target) {    int left = 0, right = ...;    while(...) {        int mid = left + (right - left) / 2;        if (nums[mid] == target) {            ...        } else if (nums[mid] < target) {            left = ...        } else if (nums[mid] > target) {            right = ...        }    }    return ...;}

其中,计算mid时需要防止溢出,代码中left + (right - left) / 2与(left + right) / 2的结果相同,但是有效防止了因left和right太大,直接相加(即:left + right)而导致的溢出情况。

基本二分查找

在一个有序(默认递增)数组中搜索一个数,如果存在,返回其索引,否则返回-1。

代码实现:

public int binarySearch(int[] nums, int target) {    int left = 0;    // 初始化right的值为nums.length - 1,即:最后一个元素的索引,而不是nums.length    int right = nums.length - 1;    // left <= right为了防止遗漏元素,如:[3,3],此时left与right相等,如果判断条件是<,则会遗漏3这个元素    while(left <= right) {        int mid = left + (right - left) / 2;        if(nums[mid] == target)            return mid;        else if (nums[mid] < target)            // mid+1是为了保证范围收缩至右边区间,因为进入该区间的条件是nums[mid]不等于target            // 即:要么在左区间,要么在右区间,且不需要包含mid            left = mid + 1;        else if (nums[mid] > target)            // mid-1的原因同上            right = mid - 1;    }    return -1;}

注意:

循环退出条件:是low<=high而不是low<high。mid的取值:low + (high-low)/2。low和high的收缩边界:low=mid+1,high=mid-1。二分查找应用场景局限性

1)二分查找依赖的是顺序表结构(即:数组)。如:链表不可以使用二分查找。

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

3)数据量太小不适合二分查找。如果要处理的数据量很小,采用顺序遍历即可,无需使用二分查找。如:在一个大小为10的数组中查找一个元素,使用二分查找和顺序遍历的查找效率基本一致。

4)数据量太大时不适合二分查找。二分查找的底层需要依赖数组这种数据结构,而数组为了支持随机访问的特性,要求内存空间连续,对内存的要求比较苛刻。如:1GB大小的数据,如果使用数组进行存储,则需要1GB的连续内存空间。

5)有序数组中存在等值元素时,返回的索引为其中的一个元素。如:有序数组nums = [1,2,2,2,3],target为2,通过二分查找算法返回的索引为2。

寻找左侧边界

在一个有序(默认递增)数组中搜索一个数,如果存在,返回其最左侧的索引,否则返回-1。

代码实现:

/** * 寻找左侧边界 * @param nums 有序数组 * @param target 目标值 * @return 目标值左侧边界下标 */public int leftBound(int[] nums, int target){    // 定义左边界    int left = 0;    // 定义右边界    int right = nums.length-1;    while (left <= right){        // 获取mid        int mid = left + (right-left)/2;        // 如果中间元素大于目标值,则继续在左区间中查找(即:收缩右边界)        if(nums[mid] > target){            right = mid-1;        }else if(nums[mid] < target){   // 如果中间元素小于目标值,则继续在右区间中查找(即:收缩左边界)            left = mid+1;        }else { // 如果中间元素等于目标值,由于需要是寻找左侧边界,则继续在左区间中查找(即:收缩右边界)            right = mid-1;        }    }    // left值越界,说明在left数组中找不到与target相等的值,返回-1    if(left < 0 || left >= nums.length){        return -1;    }    // 如果存在与目标值相等的元素,则该元素对应的下标    return nums[left] == target ? left : -1;}
寻找右侧边界

在一个有序(默认递增)数组中搜索一个数,如果存在,返回其最右侧的索引,否则返回-1。

代码实现:

/** * 寻找右侧边界 * @param nums 有序数组 * @param target 目标值 * @return 目标值右侧边界下标 */public int rightBound(int[] nums, int target){    // 定义左边界    int left = 0;    // 定义有边界    int right = nums.length-1;    while (left <= right){        // 获取mid        int mid = left + (right -left)/2 ;        // 如果中间元素大于目标值,则继续在左区间中查找(即:收缩右边界)        if(nums[mid] > target){            right = mid-1;        }else if(nums[mid] < target){   // 如果中间元素小于目标值,则继续在右区间中查找(即:收缩左边界)            left = mid+1;        }else {     // 如果中间元素等于目标值,由于需要是寻找右侧边界,则继续在右区间中查找(即:收缩左边界)            left = mid+1;        }    }    if(right < 0 || right >= nums.length){        return -1;    }    return nums[right] == target ? right : -1;}

二分查找除了寻找左右边界外,还有一些其他常用场景,如:查找第一个大于目标值的元素、查找最后一个小于目标值的元素,解题思路基本一致,在实现代码中添加补丁即可。

标签: #高效查找算法是什么 #评价查找效率的主要标准是