查找算法 订阅
查找是在大量的信息中寻找一个特定的信息元素,在计算机应用中,查找是常用的基本运算,例如编译程序中符号表的查找。 展开全文
查找是在大量的信息中寻找一个特定的信息元素,在计算机应用中,查找是常用的基本运算,例如编译程序中符号表的查找。
信息
范    围
计算机应用
解    释
寻找一个特定的信息元素
种    类
顺序、二分、分块
中文名
查找算法
查找算法概念
用关键字标识一个数据元素,查找时根据给定的某个值,在表中确定一个关键字的值等于给定值的记录或数据元素。在计算机中进行查找的方法是根据表中的记录的组织结构确定的。  顺序查找也称为线形查找,从数据结构线形表的一端开始,顺序扫描,依次将扫描到的结点关键字与给定值k相比较,若相等则表示查找成功;若扫描结束仍没有找到关键字等于k的结点,表示查找失败。  二分查找要求线形表中的结点按关键字值升序或降序排列,用给定值k先与中间结点的关键字比较,中间结点把线形表分成两个子表,若相等则查找成功;若不相等,再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表,这样递归进行,直到查找到或查找结束发现表中没有这样的结点。  分块查找也称为索引查找,把线形分成若干块,在每一块中的数据元素的存储顺序是任意的,但要求块与块之间须按关键字值的大小有序排列,还要建立一个按关键字值递增顺序排列的索引表,索引表中的一项对应线形表中的一块,索引项包括两个内容:① 键域存放相应块的最大关键字;② 链域存放指向本块第一个结点的指针。分块查找分两步进行,先确定待查找的结点属于哪一块,然后在块内查找结点。  哈希表查找是通过对记录的关键字值进行运算,直接求出结点的地址,是关键字到地址的直接转换方法,不用反复比较。假设f包含n个结点,Ri为其中某个结点(1≤i≤n),keyi是其关键字值,在keyi与Ri的地址之间建立某种函数关系,可以通过这个函数把关键字值转换成相应结点的地址,有:addr(Ri)=H(keyi),addr(Ri)为哈希函数。
收起全文
精华内容
参与话题
问答
  • 查找算法

    万次阅读 2020-08-23 12:57:53
    二分查找 public class BinarySearch { public static int rank(int key, int[] a) { int lo = 0; int hi = a.length - 1; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (key < a[mid]) hi = ...

    一、二分查找

    1.1 基本思想

    在有序表中,取中间记录作为比较对象,若给定值与中间记录的关键字相等,则查找成功;若给定值小于中间记录的关键字,则在中间记录的左半区继续查找;若给定值大于中间记录的关键字,则在中间记录的右半区继续查找。不断重复上述过程,直到查找成功,或所有查找区域无记录,查找失败为止。

    1.2 代码实现

    递归实现

    public static int BinarySearch2(int[] arr, int key, int left, int right) {
        if (left > right)
            return -1;
        int mid = left + (right - left) / 2;
        if (arr[mid] > key)
            return BinarySearch2(arr, key, left, mid - 1);
        else if (arr[mid] < key)
            return BinarySearch2(arr, key, mid + 1, right);
        else
            return mid;
    }
    

    迭代实现

    public static int BinarySearch(int[] arr, int key) {
        int left = 0, right = arr.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] > key)
                right = mid - 1;
            else if (arr[mid] < key)
                left = mid + 1;
            else
                return mid;
        }
        return -1;
    }
    

    二、插值查找

    2.1 基本思想

    插值查找是根据要查找的关键字 key 与查找表中最大最小记录的关键字比较后的查找方法,其核心就在于插值的计算公式 ( key - arr[ left ] ) / ( arr[ right ] - arr[ left ] )

    2.2 代码实现

    public static int InterpolationSearch(int[] arr, int key) {
        int left = 0, right = arr.length - 1;
        while (left < right) {
            int mid = left + (right - left) * ((key - arr[left]) / (arr[right] - arr[left]));
            if (arr[mid] > key)
                right = mid - 1;
            else if (arr[mid] < key)
                left = mid + 1;
            else
                return mid;
        }
        return -1;
    }
    

    三、斐波那契查找

    3.1 基本思想

    利用斐波那契数列进行查找。

    3.2 代码实现

    public static int fib(int N) {
        int a = 0, b = 1, c = 0;
        for (int i = 0; i < N; i++) {
            c = a + b;
            b = a;
            a = c;
        }
        return c;
    }
    
    public static int FibonacciSearch(int[] arr, int key) {
        int left = 0, right = arr.length - 1;
        int k = 0;
        while (right > fib(k) - 1)
            k++;
        int[] tempArr = new int[fib(k)];
        System.arraycopy(arr, 0, tempArr, 0, arr.length);
        for (int i = right; i < fib(k); i++)
            tempArr[i] = tempArr[right];
        while (left < right) {
            int mid = left + fib(k - 1) - 1;
            if (tempArr[mid] > key) {
                right = mid - 1;
                k -= 1;
            }
            else if (tempArr[mid] < key) {
                left = mid + 1;
                k -= 2;
            }
            else
                return Math.min(mid, right);
        }
        return -1;
    }
    

    四、二叉查找树

    4.1 基本思想

    二叉排序树,又称为二叉查找树。它或者是一颗空树,或者是具有下列性质的二叉树。

    • 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值。
    • 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值。
    • 它的左、右子树也分别为二叉排序树。

    4.2 代码实现

    结点类

    public class TreeNode {
    
        Integer key;
        Integer val;
        TreeNode left;
        TreeNode right;
    
        TreeNode(Integer key, Integer val) {
            this.key = key;
            this.val = val;
        }
    
    }
    

    递归实现

    public static int SearchBST(TreeNode root, int key) {
        if (root == null)
            return -1;
        if (key < root.key)
            return SearchBST(root.left, key);
        if (key > root.key)
            return SearchBST(root.right, key);
        return root.val;
    }
    

    迭代实现

    public static int SearchBST(TreeNode root, int key) {
        while (root != null && root.key != key)
            root = key < root.key ? root.left : root.right;
        return root == null ? -1 : root.val;
    }
    

    五、散列表查找

    5.1 基本思想

    散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系 f,使得每个关键字 key 对应一个存储位置 f(key)。查找时,根据这个确定的对应关系找到给定值 key 的映射 f(key),若查找集合中存在这个记录,则必定在 f(key) 的位置上。

    5.2 散列函数

    如果我们有一个能够保存 M 个键值对的数组,那么我们就需要一个能够将任意键转化为该数组范围内的索引([0, M - 1] 范围内的整数)的散列函数。

    要为一个数据类型实现一个优秀的散列方法需要满足三个条件:

    • 一致性:等价的键必然产生相等的散列值。
    • 高效性:计算简便。
    • 均匀性:均匀地散列所有的键。

    5.2.1 正整数

    将整数散列最常用的方法是除留余数法。我们选择大小为素数 M 的数组,对于任意正整数 k,计算 k 除以 M 的余数。

    5.2.2 浮点数

    如果键是 0 到 1 之间的实数,我们可以将它乘以 M 并四舍五入得到一个 0 至 M - 1 之间的索引值。但这种情况下键的高位起的作用更大,最低位对散列的结果没有影响。修正这个问题的办法是将键表示为二进制数然后再使用除留余数法

    5.2.3 字符串

    除数余留法也可以处理较长的键,例如字符串,我们只需将它们当作大整数即可。

    int hash = 0;
    for (int i = 0; i < s.length(); i++)
        hash = (R * hash + s.charAt(i)) % M;
    

    Java 的 charAt() 函数能够返回一个 char 值,即一个非负 16 位整数。如果 R 比仟何字符的值都 大,这种计算相当于将字符串当作一个以 4 的 R 进制值,将它除以 M 并取余。一种叫 Horner 方法的经典算法用 N 次乘法、加法和取余来计算一个字符串的散列值。只要 R 足够小,不造成溢出,那么结果就能够如我们所愿,落在 0 至 M - 1 之内。使用一个较小的素数,例如 31,可以保证字符串中的所有字符都能发挥作用。Java 的 String 的默认实现使用了一个类似的方法。

    5.2.4 组合键

    如果键的类型含有多个整型变量,我们可以和 String 类型一样将它们混合起来。例如,假设被查找的键的类型是 Date,其中含有几个整型的域:day(两个数字表示的日),month(两个数字表示的月)和year(4 个数字表示的年)。我们可以这样计算它的散列值:

    int hash = (((day * R + month) % M) * R + year) % M;
    

    只要 R 足够小不造成溢出,也可以得到一个 0 至 M - 1 之间的散列值。在这种情况下我们可以通过选择一个适当的 M,比如 31,来省去括号内的 % M 计算。和字符串的散列算法一样,这个方法也能处理有任意多个整型变量的类型。

    5.2.5 软缓存

    如果散列值的计算很耗时,那么我们或许可以将每个键的散列值缓存起来,即在键中使用一个 hash 变量来保存它的 hashCode() 的返回值。第一次调用 hashCode() 方法时,我们需要计算对象的散列值,但之后对 hashCode() 方法的调用会直接返回 hash 变量的值。

    5.3 基于拉链法的散列表

    一个散列函数能够将键转化为数组索引。散列算法的第二步是碰撞处理,也就是处理两个或多个键的散列值相同的情况。一种直接的办法是将大小为 M 的数组中的每个元素指向一-条链表,链表中的每个结点都存储了散列值为该元素的索引的键值对。这种方法被称为拉链法,因为发生冲突的元素都被存储在链表中。这个方法的基本思想就是选择足够大的 M,使得所有链表都尽可能短以保证高效的查找。查找分两步:首先根据散列值找到对应的链表,然后沿着链表顺序查找相应的键。

    5.4 基于线性探测法的散列表

    实现散列表的另一种方式就是用大小为 M 的数组保存 N 个键值对,其中 M > N。我们需要依靠数组中的空位解决碰撞冲突。基于这种策略的所有方法被统称为开放地址散列表。

    开放地址散列表中最简单的方法叫做线性探测法:当碰撞发生时(当一个键的散列值已经被另一个不同的键占用),我们直接检查散列表中的下一个位置(将索引值加 1)。这样的线性探测可能会产生三种结果:

    • 命中,该位置的键和被查找的键相同。
    • 未命中,键为空(该位置没有键)。
    • 继续查找,该位置的键和被查找的键不同。

    5.4.1 插入操作

    public void put(Key key, Value val) {
    	if (N >= M / 2) // 键值对总数大于表大小的 1/2
    		resize(2 * M); // 表扩容
    	for (int i = hash(key); keys[i] != null; i = (i + 1) % M)
    		if (keys[i].equals(key)) {
    			vals[i] = val; // 更新值
    			return;
    		}
    	keys[i] = key;
    	vals[i] = val;
    	N++;
    }
    

    5.4.2 删除操作

    在基于线性探测的散列表中删除一个键,会发现直接将该键所在的位置设为 null 是不行的,因为这会使得在此位置之后的元素无法被查找。因此,我们需要将键簇中被删除键的右侧的所有键重新插入散列表。

    public void delete(Key key) {
    	if (!contains(key))
    		return;
    	int i = hash(key);
    	while (!key.equals(keys[i]))
    		i = (i + 1) % M;
    	keys[i] = null;
    	vals[i] = null;
    	i = (i + 1) % M;
    	while (keys[i] != null) {
    		Key keyToRedo = keys[i];
    		Value valToRedo = vals[i];
    		keys[i] = null;
    		vals[i] = null;
    		N--;
    		put(keyToRedo, valToRedo);
    		i = (i + 1) % M;
    	}
    	N--;
    	if (N > 0 && N == M / 8)
    		resize(M / 2); // 调整数组大小
    }
    

    六、总结

    6.1 符号表的各种实现的优缺点总结

    符号表的各种实现的优缺点总结

    6.2 各种符号表实现的渐进性能总结

    各种符号表实现的渐进性能总结

    展开全文
  • 【算法分析】查找算法:二分查找、顺序查找

    万次阅读 多人点赞 2012-07-19 09:51:07
    08年9月入学,12年7月毕业,结束了我在软件学院愉快丰富的大学生活。...查找算法是在存在的序列(list) 中查找特定的目标(target),要求序列中每个记录必须与一个关键词(key)关联才能进行查找。

    08年9月入学,12年7月毕业,结束了我在软件学院愉快丰富的大学生活。此系列是对四年专业课程学习的回顾,索引参见:http://blog.csdn.net/xiaowei_cqu/article/details/7747205


    查找算法


    查找算法是在存在的序列(list) 中查找特定的目标(target),要求序列中每个记录必须与一个关键词(key)关联才能进行查找。

     
    查找算法通常需要两个输入:
    1、被查找的序列
    2、要查找的关键词
    查找算法的输出参数和返回值:
    1、返回类型为 Error_code 的值用以表示是否查找成功
    2、如果查找成功,返回 success, 输出参数 position 定位到目标所在位置
    3、如果查找失败,返回 not present,输出参数可能是未定义或不同于已有位置的任何值

    顺序查找算法


    顺序查找算法的思路很简单:从表的第一个元素开始一个一个向下查找,如果有和目标一致的元素,查找成功;如果到最后一个元素仍没有目标元素,则查找失败。

    【实验说明】

    题目:编写一个程序,对顺序表{3,6,2,10,1,8,5,7,4,9},采用顺序查找关键字5的过程。要求输出:
    1)原顺序表;2)查找到关键字的位置;3)进行比较的次数。
    1.首先要编写类表List。需要满足最基本的操作插入insert(),获取retrieve(),以及得到大小size()。
    2.我们观察题目要求,表中虽然存储的是简单的整数,但如果我们使用List<int>对象显然无法记录比较次数,所以我们自己写一个类Key通过其内部int类型的数据成员来记录存于表中的值,并模仿int基本的逻辑操作,即编写重载逻辑运算符,同时增加一个静态数据成员comparisons用于记录其比较操作的次数。
    3.准备工作做好之后开始编写顺序查找算法。算法的思路很简单,也较易实现,从表中第一个元素开始比较,发现目标则返回元素所在表中位置;若遍历之后没有目标,则查找失败,返回-1表示表中没有目标元素。
    4.按题目要求编写最后的输出函数。

    【相关代码】

    函数 sequential_search
    int sequential_search(const List<int> &the_list,
    					  const Key &target)
    /*Post: If an entry in the_list is equal to target, then return the position
            of this entry. 
    		Otherwise return -1 
    */
    {
    	int position;
    	int s=the_list.size();
    	for(position=0;position<s;position++){
    		int data;
    		the_list.retrieve(position,data);
    		if(data==target){
    			return position;
    		}
    	}
    	return -1;
    }
    

    二分查找算法


    二分查找前提是表是按递增或递减顺序的规范表。此次实验中我们使用的是递增表。
    二分查找从表中间开始查找目标元素。如果找到一致元素,则查找成功。如果中间元素比目标元素小,则仍用二分查找方法查找表的后半部分(表是递增排列的),反之中间元素比目标元素大,则查找表的前半部分。

    【实验说明】

    题目:编写一个程序,对有序表{1,2,3,4,5,6,7,8,9,10},采用二分查找关键字9的过程。要求输出:
    1)原顺序表;2)查找到关键字的位置;3)进行比较的次数。
    1.二分查找算法的前提是表必须是有序的,如题目中是递增方式排列的表。实现表的有序一方面是用户规范输入,另一方面我们也可以编写有序的类来方便用户的输入。
    所以从List中派生类Oredered_list,重新编写函数Error_code insert(int position,const Record &data),使插入的位置不满足表的有序条件时,不能插入。
    同时编写插入的重载函数 Error_code insert(const Record &data),可以直接插入到合适的位置,方便用户输入。
    2.仍使用题目1中的Key来表示目标
    3.实现二分查找算法。通过书中的学习,我们直接使用添加相等判断的二分查找算法。即每次从表的中间元素开始比较,如果得到目标则返回元素所在表中位置;如果中间元素小于目标元素,则对右半部分继续二分查找;反之对前半部分表进行二分查找。若最后都没有目标元素,返回-1用以表示表中没有目标元素。
    4.仍使用题目1编写的输出函数将结果输出。
    /*注意这里因为Ordered_list是从List中派生而来,所以虽然print_out函数中第一个参数类型是List<int>,仍可以使用,而不用编写重载函数*/

    【相关代码】

    函数 binary_search
    int binary_search(const Ordered_list<int> &the_list,
    					const Key &target)
    /*Post: If an entry in the_list is equal to target, then return the position
            of this entry. 
    		Otherwise return -1 
    */
    {
    	int position;
    	int data;
    	int bottom=0,top=the_list.size()-1;
    	while(bottom<=top){
    		position=(bottom+top)>>1; 
    		the_list.retrieve(position,data);
    		if(data==target)
    			return position;
    		if(data<target)bottom=position+1;
    		else top=position-1;
    	}
    	return -1;
    }

    【过程记录】

    实验截图:


    【结果分析】


    A.实现顺序查找算法

    1.顺序查找算法思路很简单,就是一种遍历的思想,一个个查找目标元素,实现也很简单。
    2.对于有n个元素的表适用顺序查找。比较次数:不成功:比较n次。成功查找:最好的情况为1次,即第一个元素即为目标元素;最差的情况为n次;平均比较次数(n+1)/2次。
    所以当表很大时,顺序查找的代价是很大的。
    3.顺序查找算法不会有重复的比较出现,即一旦找到即成功,但同时这种代价是当表中有重复的目标元素时(比如有多个目标元素)我们只能得到第一个元素的位置。

    B.实现二分查找算法

    1.二分查找法思路:递增排列的表,首先从中间元素开始查找,如果元素比目标元素小,则查找后半部分表,反之查找前半部分表,并重复这一过程。这样每次查找中我们都把表的长度减半。
    2.二分查找在实现中有量bottom和top,每次减半的过程体现在bottom和top的改变上,在代码的实现上可以使用单纯的循环或者用函数递归的思想。
    递归思想更容易理解,但编写之后我们发现函数是尾递归,尾递归通常可以用简单的循环实现,循环在操作来说没有了函数调用的过程,更节省时间和空间。
    3.编码中小小地方的改动可能对程序有很大的改观。
    如上述两种二分查找binary_search_1(不比较等于的情况)binary_search_2(添加等于情况)



    实验代码下载:http://download.csdn.net/detail/xiaowei_cqu/4437702

    (转载请注明作者和出处:http://blog.csdn.net/xiaowei_cqu 未经允许请勿用于商业用途)



    展开全文
  • 线性查找算法

    千次阅读 2015-07-29 12:25:47
    十大算法之线性查找: 介绍: BFPRT算法解决的问题十分经典,即从某n个元素的序列中选出第k大(第k小)的元素,通过巧妙的分 析,BFPRT可以保证在最坏情况下仍为线性时间复杂度。该算法的思想与快速排序思想相似...

    十大算法之线性查找:

     

    介绍:

    BFPRT算法解决的问题十分经典,即从某n个元素的序列中选出第k大(第k小)的元素,通过巧妙的分 析,BFPRT可以保证在最坏情况下仍为线性时间复杂度。该算法的思想与快速排序思想相似,当然,为使得算法在最坏情况下,依然能达到o(n)的时间复杂 度,五位算法作者做了精妙的处理。

    时间复杂度

    O(N)

     

    算法步骤:

     

    1. 将n个元素每5个一组,分成n/5(上界)组。

    2. 取出每一组的中位数,任意排序方法,比如插入排序。

    3. 递归的调用selection算法查找上一步中所有中位数的中位数,设为x,偶数个中位数的情况下设定为选取中间小的一个。

    4. 用x来分割数组,设小于等于x的个数为k,大于x的个数即为n-k。

    5. 若i==k,返回x;若i<k,在小于x的元素中递归查找第i小的元素;若i>k,在大于x的元素中递归查找第i-k小的元素。

    终止条件:n=1时,返回的即是i小元素。

     

    具体详情解析请点击:十大算法之线性查找算法


    搜索与推荐Wiki

    扫一扫 关注微信公众号!号主 专注于搜索和推荐系统,尝试使用算法去更好的服务于用户,包括但不局限于机器学习,深度学习,强化学习,自然语言理解,知识图谱,还不定时分享技术,资料,思考等文章!


                                 【技术服务】,详情点击查看:https://mp.weixin.qq.com/s/PtX9ukKRBmazAWARprGIAg


    外包服务

     

    展开全文
  • 查找算法之二分查找算法

    千次阅读 2015-07-23 08:08:49
    查找算法之二分查找算法1. 概述二分查找算法也称折半查找算法,是在有序数组中用到的较为频繁的一种查找算法。在未接触二分查找算法时,最通用的一种做法是,对数组进行遍历,跟每个元素进行比较,即顺序查找。二分...

    查找算法之二分查找算法

    1. 概述

    二分查找算法也称折半查找算法,是在有序数组中用到的较为频繁的一种查找算法。在未接触二分查找算法时,最通用的一种做法是,对数组进行遍历,跟每个元素进行比较,即顺序查找。二分查找较顺序查找更优,因为这种算法每一次比较都使查找范围缩小一半。

    2. 算法思想

    二分查找算法是建立在有序数组基础上的。算法思想为:

    1. 查找过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则查找过程结束;
    2. 如果某一待查找元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟第1点一样从中间元素开始继续进行查找。
    3. 如果在某一步骤数组为空,则代表找不到。

    1

    算法实现思路:

    1. 找出位于数组中间的值(为便于表述,将该值放在一个临时变量tmp中)。
    2. 需要找到的key和tmp进行比较。
    3. 如果key值大于tmp,则把数组中间位置作为下一次计算的起点;重复第1、2步骤继续查找。
    4. 如果key值小于tmp,则把数组中间位置作为下一次计算的终点;重复第1、2步骤继续查找。
    5. 如果key值等于tmp,则返回数组下标,完成查找。

    3. 算法实现

    package com.demo;
    
    /**
     * 二分查找算法
     * 
     * @author 小明
     *
     */
    public class BinarySearch {
    
        /**
         * 二分查找:非递归方式查找
         * 
         * @param array
         *            排序数组
         * @param key
         *            待查找元素
         * @return 查找到元素在数组中的索引,-1表示未找到
         */
        public static int search(int[] array, int key) {
            // 头指针、尾指针、中间指针
            int head = 0, tail = array.length - 1, middle;
    
            while (head <= tail) { // 头指针在尾指针之前
                middle = (head + tail) >> 1; // 通过头、尾指针位置求中间位置
                if (key > array[middle]) { // 待查找元素在中间指针元素后
                    head = middle + 1;
                } else if (key < array[middle]) { // 待查找元素在中间指针元素之前
                    tail = middle - 1;
                } else { // 待查找元素与中间指针元素相等
                    return middle;
                }
            }
    
            return -1; // 返回-1表示未找到
        }
    
        /**
         * 入口方法,测试
         * @param args
         */
        public static void main(String[] args) {
            int[] array = {3, 7, 9, 12, 87, 99, 126};
            int key = 87;
            int index = search(array, key);
            if (index != -1){
                System.out.println("查找到在数组中的索引:" + index);
            } else {
                System.out.println("未查找到该元素");
            }
        }
    }

    上述示例是使用非递归的方式实现二分查找,当然也可以使用递归的方式来实现:

        /**
         * 二分查找:递归实现
         * 
         * @param array
         *            排序数组
         * @param key
         *            待查找元素
         * @param head
         *            头指针索引
         * @param tail
         *            尾指针索引
         * @return 查找到元素在数组中的索引,-1表示未找到
         */
        public static int search(int[] array, int key, int head, int tail) {
            if (head > tail) { // 头指针在尾指针之后,说明找不到元素
                return -1;
            }
            int middle = (head + tail) >> 1; // 通过头、尾指针索引求中间位置索引
            if (key > array[middle]) { // 待查找元素在中间指针元素后
                return search(array, key, middle + 1, tail);
            } else if (key < array[middle]) { // 待查找元素在中间元素之前
                return search(array, key, head, middle - 1);
            } else { // 待查找元素与中间指针元素相等
                return middle;
            }
        }
    展开全文
  • 1. 顺序查找 2. 二分查找 3. 插值查找 4. 斐波那契查找 5. 树表查找 6. 分块查找 7. 哈希查找
  • linux查找文件夹命令

    万次阅读 2017-12-22 10:16:11
    查找命令: 查找根目录下查找文件夹名称叫www.91cnm.com的目录地址find / -name www.91cnm.com -d查找/var/www/目录下叫index.php的文件find /var/www/ -name index.php 查找根目录下所有已”.sh”结尾的文件find...
  • 查找算法】折半查找法

    千次阅读 2020-02-20 17:08:09
    本篇文章将介绍折半查找算法。 文章目录何为折半查找?算法实现递归实现效率分析 何为折半查找? 上一篇文章介绍了顺序查找算法,我们知道,虽然顺序查找算法适用性高,但效率太低,那么能不能在此基础上继续提高...
  • 插值查找算法介绍插值查找(Interpolation Search)是根据要查找关键字key与查找表中最大最小记录的关键字比较后的查找方法,其核心就在于插值的计算公式key-arr[low]/arr[high]-arr[low]。细看是不是key在整序列中...
  • 查找算法】顺序查找法

    千次阅读 2020-02-20 15:30:28
    学到这里,相信大家对基本的数据结构都有了一定的认识,当然,我们还有一些...本篇文章将介绍顺序查找算法。 文章目录何为顺序查找?算法改进时间效率分析 何为顺序查找? 看到这个算法的名字不难理解,它是一种按...
  • 折半查找算法介绍折半查找(Binary Search)又称为二分查找。它的前提是线性表中的记录必须是关键码有序(通常从小到大有序),线性表必须采用顺序存储。从算法名称可以看出算法的思路,先取有序序列中间值与查找值...
  • 算法背景有时候,可能会遇到这样的表:整个表中的元素未必有序,但若划分为若干块后,每一块中的所有元素均小于(或大于)其后面块中的所有元素。我们称这种为分块有序。对于分块有序表的查找首先,我们需要先建立一...
  • 二分查找算法

    千次阅读 2015-07-29 10:44:54
    二分查找算法是在有序数组中用到的较为频繁的一种算法,在未接触二分查找算法时,最通用的一种做法是,对数组进行遍历,跟每个元素进行比较,其时间为O(n).但二分查找算法则更优,因为其查找时间为O(lgn),譬如数组{...
  • 最近邻查找算法kd-tree

    万次阅读 多人点赞 2016-08-12 10:12:01
    海量数据最近邻查找的kd-tree简介  利用Octree,為封閉的3D空間建立一個資料結構來管理空間中的每個元素。如此我們可以在 O(log N) 的時間內對這3D空間進行搜尋。  3D空間可以用Octree,2D空間可以用Quadtree(四...
  • 有序表查找---折半查找算法

    千次阅读 2019-03-10 20:00:31
    折半查找概念 折半查找,又称二分查找。 前提是线性表中的记录必须是关键码有序(由小到大或由大到小),线性表必须采用顺序存储。 折半查找的基本思想是:在有序表中,取中间值为比较对象,如果给定的值和中间值的...
  • java选择算法、java查找算法汇总

    千次阅读 2017-02-07 13:44:09
    线性查找顺序查找适合于存储结构为顺序存储或链接存储的线性表public static int query(int[] arrays, int target){ for(int i = 0 ;i ; i ++){ if(arrays[i] == target)return i; } return -1;//没找到 }线性...
  • 查找算法】二叉排序树查找法

    千次阅读 2020-02-21 16:03:32
    本篇文章将介绍二叉排序树的查找算法。 文章目录何为二叉排序树查找?查找算法实现查找效率分析二叉排序树的插入操作二叉排序树的生成操作二叉排序树的删除操作 何为二叉排序树查找? 上篇文章我们学习了折半查找,...
  • 查找算法之线性表查找

    千次阅读 2015-08-29 21:26:21
    一 基本概念 查找表:由同一类型的数据元素构成的集合。 静态查找表:支持的操作:(1)查询特定的元素是否在查找表中。(2)检索某个特定的元素的各种属性。(1)(2)操作统称为“查找”操作。...二 线性表查找算法
  • 查找算法——折半查找

    万次阅读 2017-05-31 21:04:03
    这个查找算法的特点,就是,要求数据要是有序的。1 ,存储结构一定是顺序存储 2 ,关键字大小必须有序排列然后,利用这组有序的数据之间的关系,来进行折半的查找。比方说,这组数据是升序排列的。一开始,首先...
  • 每天学一点算法-线性查找算法

    千次阅读 2014-11-29 10:41:59
    线性查找算法 定义 BFPRT 算法解决的问题十分经典,即从某n个元素的序列中选出第k大(第k小)的元素,通过巧妙的分析,BFPRT 可以保证在最坏情况下仍为线性时间复杂度。该算法的思想与快速排序思想相似,当然,...
  • 查找算法之哈希查找

    万次阅读 多人点赞 2012-07-01 11:56:12
    哈希查找是通过计算数据元素的存储地址进行查找的一种方法。O(1)的查找,即所谓的秒杀。哈希查找的本质是先将数据映射成它的哈希值。哈希查找的核心是构造一个哈希函数,它将原来直观、整洁的数据映射为看上去似乎是...
  • 时间复杂度:如果要查找的记录在右侧,则左边的数据都不用在哦按段了,不断反复进行下去,对处于当中的大部分数据源,其工作效率要高一些所以尽管斐波那契查找的时间复杂度也为O(logn)。但品均性能上来说,斐波那契...
  • 折半查找是我很喜欢的一种查找方式,它代码简单,查询效率很高,时间复杂度是0(log2n). 折半查找是在一个有序的元组中查找元素,它通过关键词与中间值的比较,来查找相关的元素。如果关键词比中间值大,那么就在元组...
  • 查找算法之二分法查找

    千次阅读 2016-12-03 12:00:10
    在二分查找算法中,数列已经排好序,对于要搜索的数字,我们从中间的数开始搜索,如果目标数小于中间数,则无需搜索右边的数,因为右边的数都大于中间的数,直接搜索左边的数就可以;如果目标数大于中间数,则无需...
  • DxR路由查找算法前传

    千次阅读 2015-02-15 11:25:19
    你认为现在携带现代操作系统的通用计算机中哪类计算看上去是且必须是超级快的,毫无疑问,答案是内存访问。你认为现在携带现代操作系统的通用计算机中哪类计算看上去是且理论上超级慢的,毫无疑问,答案是路由寻址。...

空空如也

1 2 3 4 5 ... 20
收藏数 523,027
精华内容 209,210
关键字:

查找算法