优站点网址收录网,谁可以做网站优化排名推广,宁波网站建设计,中山网站上排名引导 经过前面几节排序内容#xff0c;我们开始接触查找算法--二分查找。 二分查找的时间复杂度是O(logn)#xff0c;是一个非常高效的算法。虽然理解起来很容易#xff0c;但是真正想要熟练掌握就没那么简单了。
二分查找
二分查找原理#xff1a; 首先#xff0c;假设…引导 经过前面几节排序内容我们开始接触查找算法--二分查找。 二分查找的时间复杂度是O(logn)是一个非常高效的算法。虽然理解起来很容易但是真正想要熟练掌握就没那么简单了。
二分查找
二分查找原理 首先假设表中元素是按升序排列将表中间位置记录的关键字与查找关键字比较如果两者相等则查找成功否则利用中间位置记录将表分成前、后两个子表如果中间位置记录的关键字大于查找关键字则进一步查找前一子表否则进一步查找后一子表。重复以上过程直到找到满足条件的记录使查找成功或直到子表不存在为止此时查找不成功。
这和我们的归并排序快速排序的思想是不是很相似。 includestdlib.h #includestdio.h #includestring.h int binarysearch(int a[],int len , int value) { int low 0; int high len - 1; int mid low (high - low)/2; while(a[mid] ! value) { if(low high) return -1; if(a[mid] value) high mid - 1; else if(a[mid] value) low mid 1; mid low (high - low)/2; } return mid; } int main() { int a[10] {1,5,8,10,13,15,16,18,19,20}; printf(index %d\n,binarysearch(a,10,16)); return 0; }
分析 通过上面代码的实现我相信大家对二分查找有了一定的了解。但是心细的朋友肯定会发现这个代码只能确认数组中是否有目标值若有相同的元素则不能确定返回第一个。
因此接下来我们再来练习一下二分法的几个变体
查找第一个等于给定值的元素查找最后一个等于给定值的元素查找第一个大于给定值的元素查找最后一个小于给定值的元素
其实34就是1和2前移或后移的问题我们主要练习前两个。 / *查找第一个等于给定值的元素* / int findfirstvalue(int a[],int len , int value) { int low 0; int high len - 1; int mid low (high - low)/2; while(1) { if(low high) return -1; if(a[mid] value) high mid - 1; else if(a[mid] value) low mid 1; else { if(mid0 || (a[mid-1] ! value)) return mid; else high mid - 1; } mid low (high - low)/2; } return mid; } int main() { int a[10] {1,5,8,10,15,15,15,18,19,20}; printf(index %d\n,findfirstvalue(a,10,15)); return 0; } / *查找最后一个等于给定值的元素* / int findlastvalue(int a[],int len , int value) { int low 0; int high len - 1; int mid low (high - low)/2; while(1) { if(low high) return -1; if(a[mid] value) high mid - 1; else if(a[mid] value) low mid 1; else { if(mid0 || (a[mid1] ! value)) return mid; else low mid 1; } mid low (high - low)/2; } return mid; } int main() { int a[10] {1,5,8,10,15,15,15,18,19,20}; printf(index %d\n,findlastvalue(a,10,15)); return 0; }
注意二分查找虽然效率很高但是它受限很多使用起来也不是很方便主要有以下几个原因
1. 二分查找依赖于数组 我们知道数组在内存中是连续存储的如果二分查找依赖于数组。这无疑给自己造成很大的局限性。因为当数据量很大时也就说明需要一个很大的数组这是一个很高的要求
2. 二分查找依赖于数据的有序并且静态 二分查找针对的数据时有序的。当面对的数组时无序的时候该怎么办呢我们通过之前的排序算法可以知道排序最快通用的时间复杂度是O(nlogn)。当数组没有频繁的插入删除操作我们先排序再二分查找这样也是可以接受的。但是当数组面临常插入和删除的操作时就不太适用了。会导致事件复杂度上升。
总结 本章我们开始介绍了二分查找分析了代码实现以及一些二分查找的变体。也介绍了二分查找适合的场景以及局限性。二分查找依赖有序的数组对于太大或太小的数组都不太适用太小没必要太大没有空间。并且不适合频繁的数据插入和删除操作。
