二分查找算法可以适用于模糊查找吗

问题描述

有这样的需求:一组排序好的数据放在一个数组里,用模糊匹配条件可以匹配一块连续的数据,现在需要根据某个模糊匹配条件来找到对应的一组数据。这个算法应该怎么设计比较好呢?目前的一种办法是用二分查找:先二分找到某一个匹配的元素(index为M),在(0,M)范围内进行多次二分,一直到找到上边界为止;下一步在(M,N)范围内进行多次二分,一直到找到下边界为止。这个方法会有问题吗?

解决方案

解决方案二:
不可以
解决方案三:
模糊查询来是要查询所有的数据,如dell...hellhello...xell如果你要查询ell,肯定是要搜索所有的数据,二分法没有办法解决此问题。
解决方案四:
不行如你要查找abcaabc和abcx分别在二分的两头,但是你都要匹配
解决方案五:
引用2楼inhibitory的回复:

模糊查询来是要查询所有的数据,如dell...hellhello...xell如果你要查询ell,肯定是要搜索所有的数据,二分法没有办法解决此问题。

学习了
解决方案六:
谢谢大家。说的不太清楚。举个例子:比如数据是字符串,需要找以T开始的所有字符串(也就是"模糊匹配条件可以匹配一块连续的数据")。当然实际情况要更复杂一些。
解决方案七:
谢谢大家的帮助,我要处理的情况是:匹配的数据是在一个连续的区域内,最终是用多次二分找到的上下边界。先找边界是为了能在某种情况下提高点效率,不是必须的。

时间: 2024-11-22 19:57:07

二分查找算法可以适用于模糊查找吗的相关文章

使用PHP实现二分查找算法代码分享

第一种方法: [二分查找要求]:1.必须采用顺序存储结构 2.必须按关键字大小有序排列. [优缺点]折半查找法的优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难.因此,折半查找方法适用于不经常变动而查找频繁的有序列表. [算法思想]首先,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功:否则利用中间位置记录将表分成前.后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表. 复制代码 代码如下: <?

使用PHP实现二分查找算法代码分享_php技巧

第一种方法: [二分查找要求]:1.必须采用顺序存储结构 2.必须按关键字大小有序排列. [优缺点]折半查找法的优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难.因此,折半查找方法适用于不经常变动而查找频繁的有序列表. [算法思想]首先,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功:否则利用中间位置记录将表分成前.后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表. 复制代码 代码如下: <?

JavaScript使用二分查找算法在数组中查找数据的方法_javascript技巧

本文实例讲述了JavaScript使用二分查找算法在数组中查找数据的方法.分享给大家供大家参考.具体分析如下: 二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好:其缺点是要求待查表为有序表,且插入删除困难.因此,折半查找方法适用于不经常变动而查找频繁的有序列表.首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功:否则利用中间位置记录将表分成前.后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一

[算法]二分查找算法

[思想] 二分搜索主要解决的问题是确定排序后的数组x[0,n-1]中是否包含目标元素target. 二分搜索通过持续跟踪数组中包含元素target的范围(如果target存在数组中的话)来解决问题. 一开始,这个范围是整个数组,然后通过将target与数组中的中间项进行比较并抛弃一半的范围来缩小范围.该过程持续进行, 直到在数组中找到target或确定包含target的范围为空时为止.在有n个元素的表中,二分搜索大约需要执行lgn次比较操作. 提供充足的时间,竟然只有10%的专业程序员能够将这个

Python实现二分查找算法实例

  本文实例讲述了Python实现二分查找算法的方法.分享给大家供大家参考.具体实现方法如下: ? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #!/usr/bin/env python import sys def search2(a,m): low = 0 high = len(a) - 1 while(low <= high): mid = (low + high)/2 midval = a[mid] if midval <

Java实现二分查找算法实例分析_java

本文实例讲述了Java实现二分查找算法.分享给大家供大家参考.具体如下: 1. 前提:二分查找的前提是需要查找的数组必须是已排序的,我们这里的实现默认为升序 2. 原理:将数组分为三部分,依次是中值(所谓的中值就是数组中间位置的那个值)前,中值,中值后:将要查找的值和数组的中值进行比较,若小于中值则在中值前面找,若大于中值则在中值后面找,等于中值时直接返回.然后依次是一个递归过程,将前半部分或者后半部分继续分解为三部分.可能描述得不是很清楚,若是不理解可以去网上找.从描述上就可以看出这个算法适合

二分查找算法及其变种

前言 二分查找算法也称为折半查找算法,是一种在查找算法中普遍使用的算法.其算法的基本思想是:在有序表中,取中间的记录作为比较关键字,若给定值与中间记录的关键字相等,则查找成功:若给定的值小于中间记录的关键字,则在中间记录的左半区间继续查找:若给定值大于中间记录的关键字,则在中间记录的右半区间继续查找:不断重复这个过程,直到查找成功.否则查找失败.这个思想与孔子中的中庸思想和相似. 二分查找算法的实现 基于上述的思想,可以很快写出如下代码: public int binarySearch(int[

90%的程序员无法正确实现二分查找算法???

     前言            ProgrammingPearls(<编程珠玑>)一书的作者Jon Bentley曾经说过类似的话:"90%的程序员无法正确实现二分查找算法..."      言下之意,只有1/10的程序员能够写出"二分查找算法"来.昨天我突然又看到了这句话,于是就随时打开eclipse写下了,还算顺利. 关于"二分查找算法" "二分查找算法",很多地方也被称作是"折半查找"

PHP二分查找算法示例【递归与非递归方法】_php技巧

本文实例讲述了PHP二分查找算法.分享给大家供大家参考,具体如下: binarySearch 二分查找采用的方法比较容易理解,以数组为例: ① 先取数组中间的值floor((low+top)/2), ② 然后通过与所需查找的数字进行比较,若比中间值大,则将首值替换为中间位置下一个位置,继续第一步的操作:若比中间值小,则将尾值替换为中间位置上一个位置,继续第一步操作 ③ 重复第二步操作直至找出目标数字 比如从1,3,9,23,54 中查找数字23, 首位置为0, 尾位置为4,中间位置就为2 值为9