前言:
现时我们对“高效查找算法是什么”大概比较注重,同学们都想要知道一些“高效查找算法是什么”的相关内容。那么小编同时在网络上收集了一些关于“高效查找算法是什么””的相关文章,希望同学们能喜欢,同学们快快来了解一下吧!二分查找
二分查找针对的是一个有序的数据集合,查找思想有点类似分治思想,每次通过与区间的中间元素比较,将待查找的区间缩小为原来的一半,直到找到要查找的元素或区间缩小到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;}
二分查找除了寻找左右边界外,还有一些其他常用场景,如:查找第一个大于目标值的元素、查找最后一个小于目标值的元素,解题思路基本一致,在实现代码中添加补丁即可。
标签: #高效查找算法是什么 #评价查找效率的主要标准是