最基本的查找方法就是顺序查找与二分查找,二分查找可以进一步优化为插值查找
顺序查找
最简单的查找方法,逐个比较过来
public static int seqSearch(int[] arr, int key){ for (int i=0; i<arr.length; i++){ if (key == arr[i]) return i; } return -1; }
二分查找
针对已经有序的数组,可以使用二分查找,又称折半查找
public static int binarySearch(int[] arr, int key){ int low =0; int high = arr.length -1; while(low <= high){ int mid = (low + high)/2; ++bcount; if (key>arr[mid]) { low = mid + 1; } else if (key ==arr[mid]){ return mid; } else { high = mid -1; } } return -1; }
插值查找
在折半查找中, mid = (low + high)/2 = low + (high - low)/2,我们将右边的1/2替换为 (key-arr[low])/(arr[high]-arr[low])
- 当key ==arr[low]的时候 mid = low, mid往最左边移动
- 当key== arr[high]的时候, mid=high, mid往最右边活动
可见这是一种更聪明更有倾向性的查找方法
public static int chazhiSearch(int[] arr, int key){ int low =0; int high = arr.length -1; while(low <= high){ ++ccount; int mid = low + ((key-arr[low])*(high-low)/(arr[high]-arr[low])); if (key>arr[mid]) { low = mid + 1; } else if (key ==arr[mid]){ return mid; } else { high = mid -1; } } return -1; }
测试代码
public static void main(String[] args) { int[] array = new int[]{1,2,3,4,5,6,8,9,12,15,18,20}; assert(seqSearch(array, 9) == 7); assert(seqSearch(array, 8)== -1); System.out.println(binarySearch(array, 18)); System.out.println(chazhiSearch(array, 18)); System.out.println("bcount: " + bcount); System.out.println("ccount: " + ccount); }
运行结果:
10 10 bcount: 3 ccount: 2
对于这种分布比较均匀的数列,插值查找的次数要比二分查找少
相关推荐
3种查找算法,顺序查找 折半查找 索引查找,c语言编写,可直接运行
讲述了数据结构中的几种查找算法,比如二分查找算法等,分析了其平均长度,时间以及空间开销
数据结构之查找算法.ppt
自己整理的用C语言写的数据结构和排序查找算法。数据结构包括:栈,队列,两个队列实现一个栈,两个栈实现一个队列,二叉树的创建,添加,平衡二叉树天界旋转等,红黑树,创建,添加节点,删除节点,调整。算法包括...
几种简单常用的查找算法,饱含binsearch,bstree,Hash,seqsearch。
数据结构 查找 源代码 二分查找的算法源码,两种算法的效率比较
整理的数据结构里的各种查找算法,适合面试,考试复习。
数据结构-查找算法(代码+报告)
主要包含冒泡 插入 选择 希尔 快速排序 堆排序 折半查找等常用的数据结构排序算法的实现
该部分代码实现了数据结构课程查找一章几乎所有的算法,对学习数据结构查找算法的程序实现有很好的帮助
哈希表算法实现的C语言源程序 数据结构课程设计用
数据结构——折半查找算法
常用查找详细算法 包括顺序查找,二分查找,分块查找,二叉排序树查找,哈希查找
数据结构中查找和排序算法具体的实验报告。
本书分为基本概念、简单数据结构(线性表、栈、队列)、复杂数据结构(树、图)和算法与数据结构应用(排序、查找、算法设计基础)四部分,详细介绍了常用数据结构和算法的基本概念及其不同的实现方法,对各种数据...
数据结构各种查找排序算法的实现 以及有关数据结构的试卷,习题 ,答案等
C++数据结构经典查找算法总结,包含详细可执行代码以及算法讲解!
掌握折半查找的概念和算法,了解它与其它查找方法的区别
算法方面的内容包括选择算法、查找算法、排序算法。本书还较为详细地分析了各种算法的时间复杂度和空间复杂度,介绍了分摊复杂度分析技术。作为各种数据结构和算法的应用,本书给出了图的标准界面及其实现。利用这个...
合肥工业大学数据结构 查找实验 编写算法实现下列问题的求解。 (1) 对下列数据表,分别采用二分查找算法实现查找,给出查找过程依次所比较的元素,并以二分查找的判定树来解释。 (2) 设计出在二叉排序树中插入结点的...