博客访问： 318389
博文数量： 93
博客积分： 848
博客等级： 军士长
技术积分： 1833
注册时间：
IT168企业级官微
微信号：IT168qiye
系统架构师大会
微信号：SACC2013
分类： C/C++
大家对于二分查找并不陌生，一般意义上的二分查找，往往返回给我们的是目标元素在排序数组中出现的一个随机的位置，但是在很多时候，我们却是需要目标元素的第一个和最后一个位置，才有意义。举个例子来说，我们要求得目标元素在排序数组中出现的次数，假如利用一般的方法，逐个比较目标元素和数组元素，时间复杂度O（n），不能够令我们满意，既然数组是排序的我们很容易想到二分查找，在这里我们能不能使用二分查找的算法呢，答案是肯定的。只要我们能够利用二分查找找到目标元素出现的第一个和最后一个位置，就能够求得它出现的次数。我们如何来求得目标元素出现的第一个和最后一个位置呢，其实很简单，我们只需要对于二分查找的退出条件，做一个简单的设定就能得到我们理想的结果哦！
下面我们来看一下代码:
int GetFirstK(int *a, int _left, int _right, int dest)
&&&&if(_left > _right || a == NULL)
&&&&&&&&return 0;
&&&&int temp = 0;
&&&&int left = _left;
&&&&int right = _right;
&&&&while(left < right)
&&&&&&&&temp = (left + right) >> 1;
&&&&&&&&if(a[temp] < dest)
&&&&&&&&&&&&left = temp + 1;
&&&&&&&&else
&&&&&&&&&&&&right = temp;
&&&&return left;
在这里跟一般的二分查找的代码相比，仅仅是判断语句上做了一点细微的变化，序列是递增排列的，当中间值小于目标元素的时候，目标元素在序列的右边：left = temp + 1；
其余的情况目标值在序列的左边：right = temp；我们要查找的第一个目标元素的位置，一般的情况就是目标元素存在多个情况，由上述的两个判断条件，我们可以知道，如果查找到了目标元素，并且该目标元素不是第一个的时候，此时left<right，判断继续进行。我们这里设置的判断条件保证了，当中间值小于目标元素的时候，left一定会向右移动，同时如果中间值恰好等于目标元素的时候，right能够不动，最终序列结束的时候，left=right=目标元素的第一次出现的位置！整个过程大家可以设定一个例子在纸上模拟一下：
去最后一次出现的位置，道理也是类似的：
int GetUpK(int *a, int _left, int _right, int dest)
&&&&if(_left > _right || a == NULL)
&&&&&&&&return 0;
&&&&int temp = 0;
&&&&int left = _left;
&&&&int right = _right;
&&&&while(left < right)
&&&&&&&&temp = (left + right + 1) >> 1; //保证取到中间靠后的位置
&&&&&&&&if(a[temp] > dest)
&&&&&&&&&&&&right = temp - 1;
&&&&&&&&else
&&&&&&&&&&&&left = temp;
&&&&return right;
大家可以看出，跟我们取第一个元素时候的判断条件恰好相反，而两种情况处理的方式我们可以归结为以下两句话：
1、当我们要找到目标元素出现的第一个位置时候：当中间值大于等于目标元素的时候，我们要保留当前中间值的位置，并且在左边继续查找。
这句话用条件语句表述就是：
if（a【mid】 >= dest)
2、当我们要找目标元素出现的最后一个位置的时候：当中间值小于等于目标元素的时候，我们要保留中间值的位置，并且在右边继续查找。
if(a[mid] <= dest)
阅读(1127) | 评论(0) | 转发(0) |
相关热门文章
给主人留下些什么吧！~~
请登录后评论。& 浏览内容strpos &#8212;
找出字符串第一次出现的位置（从左到右查找）
作者：C.K.
strpos(PHP 3, PHP 4, PHP 5)strpos &#8212;
（从左到右查找）说明int strpos ( string haystack, mixed needle [, int offset] )传回参数 needle在字符串 haystack中第一次出现的位置，以数字表示。不像strrpos( )，此函数可以取参数 needle全部的字符串，而且会使用全部的字符串。如果找不到参数 needle，则传回 false。参数 offset 可省略，用来表示从 offset 开始找。
语法从开头到末尾查找字符串中指定字符StrPos(&#39;源字符串&#39;,&#39;要查找的字符&#39;)从指定开始处查找StrPos(&#39;源字符串&#39;,&#39;要查找的字符&#39;,查找的开始位置)警告本函数可能返回布尔值 FALSE，但也可能返回一个与 FALSE 等值的非布尔值，例如 0 或者 &#8220;&#8221;。请参阅布尔类型章节以获取更多信息。应使用 === 运算符来测试本函数的返回值。注: 该函数可安全用于二进制对象。例子 1. strpos() examples1234567891011121314151617$mystring = 'abc'; $findme & = 'a'; $pos = strpos&#40;$mystring, $findme&#41;;
// Note our use of ===. &Simply == would not work as expected // because the position of 'a' was the 0th (first) character. if &#40;$pos === false&#41; &#123; & & echo &The string '$findme' was not found in the string '$mystring'&; &#125; else &#123; & & echo &The string '$findme' was found in the string '$mystring'&; & & echo & and exists at position $pos&; &#125;
// We can search for the character, ignoring anything before the offset $newstring = 'abcdef abcdef'; $pos = strpos&#40;$newstring, 'a', 1&#41;; // $pos = 7, not 0 ?&如果参数 needle不是字符串时，它会转换成整数并且按照字符的顺序值来使用。参数 offset允许你去指定在 haystack中从那一个字符开始搜寻，传回的位置依然是相对于 haystack的起点。参见 strrpos(), stripos(), strripos(), strrchr(), substr(), stristr(), and strstr().另：可以用中文的。只不过按照常理的一个汉字占两个字母位……例如：<?$foo=&#8221;这是一个例子，测试用。&#8221;;$num=strpos($foo,&#8221;个&#8221;);echo&#8221;$num&#8221;;?>你看到的结果是6。为什么会这样？因为他是采用数组保存的（我猜应该是），所以是以&#43;开头的。也就是说，如果$foo=&#8221;this is a sample,just for test.&#8221;;$num=strpos($foo,&#8221;t&#8221;);结果将是0，对，没错。所以使用该函数注意两点：一，可以应用于中文（PHP中文手册说明有误）；二，他的计算方式。如果想计算一个英文串中字符出现在第几个，$num++如果是中文，$num=($num+1)/2（这个并不全对，还要考虑一下标点符号全角半角的问题，自己想想吧）还要注意，不仅可以应用中文字，还可以应用中文字符传串（既然一个中文字可以，几个当然也可以了）。（手册中“一个字元”何解？？？） 相关日志PHP 字符串操作入门教程 strstr &#8212;
返回字符串中某字符串开始处至结束的字符串 is_string &#8212; 检测变量是否是字符串 strstr &#8212; 返回字符串中某指定字符到结束处的字符串
推介 SSD Cloud Server
[月考]六年级数学下册调研测试卷（三）
[月考]六年级数学下册调研测试卷（二）
[月考]六年级数学调研测试卷（一）
;2016学年度第一学期期末调研考试小学六年级数学试卷
wordpress获取文章浏览次数及本站浏览总数
PHP学习计划
学年度第一学期教学效果检测小学数学六年级试卷
毕业班学生评价
Macromedia Studio 8.0简体中文零售版
万能优盘修复工具, 能修复一切非物理损坏的优盘
Tstyle主题修改版（增加管理后台）
犀牛4.0第四次修正版 [简体中文]
聚生网管 &#8212; 局域网各用户流量监控及上网控制
飞信SMS2短信发送平台&#8211;PHP版（完整代码）
逍遥网店系统3.0标准版 (可正常使用,无任何限制)
Dreamhost空间分享计划
爱同步、金山快盘、115同步盘、酷盘、Q盘使用对比
yum错误&#8212;TypeError: rpmdb open failed
Windows XP 开始→运行→命令集锦
慢性鼻炎包括哪几种鼻病？
Windows右下角声音等图标不出现的解决办法
忘记MySQL root密码的解决方案
慢性鼻炎的日常保健
acos &#8212; 反余弦
标签云 Tag Cloud 网站统计 Statistics 广告区 Guǎng GàoR语言中怎样求得某个元素在向量中首次出现的位置_百度知道广东省“六校联盟”2016届高三第三次联考文综地理试题_图文_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
高中精品题库
最新高考模拟题
名校精品试卷
广东省“六校联盟”2016届高三第三次联考文综地理试题
上传于||文档简介
&&广&#8203;东&#8203;省&#8203;“&#8203;六&#8203;校&#8203;联&#8203;盟&#8203;”&#03;0&#03;6&#8203;届&#8203;高&#8203;三&#8203;第&#8203;三&#8203;次&#8203;联&#8203;考&#8203;文&#8203;综&#8203;地&#8203;理&#8203;试&#8203;题
阅读已结束，如果下载本文需要使用3下载券
想免费下载本文？
定制HR最喜欢的简历
下载文档到电脑，查找使用更方便
还剩6页未读，继续阅读
定制HR最喜欢的简历
你可能喜欢博客访问： 698118
博文数量： 1721
注册时间：
IT168企业级官微
微信号：IT168qiye
系统架构师大会
微信号：SACC2013
分类： 数据库开发技术
PL/SQL InStr函数　　返回某字符串在另一字符串中第一次出现的位置。　　InStr([start, ]string1, string2[, compare]) 　　参数　　start 可选项。数值表达式，用于设置每次搜索的开始位置。如果省略，将从第一个字符的位置开始搜索。如果start包含Null，则会出现错误。如果已指定compare，则必须要有start参数。　　string1 必选项。接受搜索的字符串表达式。　　string2 必选项。要搜索的字符串表达式。　　compare 可选项。指示在计算子字符串时使用的比较类型的数值。有关数值，请参阅"设置"部分。如果省略，将执行二进制比较。　　设置　　compare参数可以有以下值：　　常数 值 　　描述　　vbBinaryCompare　 　0 　　执行二进制比较。　　vbTextCompare 　 　1 　　执行文本比较。　　返回值　　InStr函数返回以下值：　　如果 InStr返回　　string1为零长度　 　0 　　string1为Null 　 　Null 　　string2为零长度　 　start 　　string2为Null 　 Null 　　string2没有找到　 　0 　　在string1中找到string2 　　找到匹配字符串的位置　　start > Len(string2) 　 　0 [@more@]SQL Server中 CHARINDEX和PATINDEX用法CHARINDEX 和PATINDEX函数常常用来在一段字符中搜索字符或者字符串。如果被搜索的字符中包含有要搜索的字符，那么这两个函数返回一个非零的整数，这个整数是要搜索的字符在被搜索的字符中的开始位数。PATINDEX函数支持使用通配符来进行搜索，然而CHARINDEX不支持通佩符。接下来，我们逐个分析这两个函数。如何使用CHARINDEX函数CHARINDEX函数返回字符或者字符串在另一个字符串中的起始位置。CHARINDEX函数调用方法如下：CHARINDEX ( expression1 , expression2 [ , start_location ] )Expression1是要到expression2中寻找的字符中，start_location是CHARINDEX函数开始在expression2中找expression1的位置。CHARINDEX函数返回一个整数，返回的整数是要找的字符串在被找的字符串中的位置。假如CHARINDEX没有找到要找的字符串，那么函数整数“0”。让我们看看下面的函数命令执行的结果：CHARINDEX('SQL', 'Microsoft SQL Server')这个函数命令将返回在“Microsoft SQL Server”中“SQL”的起始位置，在这个例子中，CHARINDEX函数将返回“S”在“Microsoft SQL Server”中的位置11。接下来，我们看这个CHARINDEX命令：CHARINDEX('7.0', 'Microsoft SQL Server 2000')在这个例子中，CHARINDEX返回零，因为字符串“7.0” 不能在“Microsoft SQL Server”中被找到。接下来通过两个例子来看看如何使用CHARINDEX函数来解决实际的T-SQL问题。第一个例子，假设你要显示Northwind数据库Customer表前5行联系人列的Last Name。这是前5行数据ContactName------------------------------ Maria AndersAna TrujilloAntonio MorenoThomas HardyChristina Berglund你可以看到，CustomName包含客户的First Name和Last Name，它们之间被一个空格隔开。我用CHARINDX函数确定两个名字中间空格的位置。通过这个方法，我们可以分析ContactName列的空格位置，这样我们可以只显示这个列的last name部分。这是显示Northwind的Customer表前5行last name的记录！select top 5 substring(ContactName,charindex(' ',ContactName)+1 ,len(ContactName)) as [Last Name] from Northwind.dbo.customers下面是这个命令输出的结果。Last Name------------------------------ AndersTrujilloMorenoHardyBerglundCHARINDEX函数找到First Name和Last Name之间的空格，所以SUBSTRING函数可以分开ContactName列，这样就只有Last Name被选出。我在CHARINDEX函数返回的整数上加1，这样Last Name不是从空格开始。在第二个例子中，即如说你要计算记录中，某一个字段包含特定字符的所有记录数。CHARINDEX函数可以方便的解决你的问题。计算 Northwind.dbo.Customer表中Addresses字段中包含单词Road或者它的缩写Rd的记录数，选择语句类似这样：SELECT count(*) from Northwind.dbo.Customers WHERE CHARINDEX('Rd',Address) > 0 or CHARINDEX('Road',Address)> 1如何使用PATINDEX函数PATINDEX函数返回字符或者字符串在另一个字符串或者表达式中的起始位置，PATINDEX函数支持搜索字符串中使用通配符，这使PATINDEX函数对于变化的搜索字符串很有价值。PATINDEX函数的命令如下：PATINDEX ( '%pattern%' , expression )Pattern是你要搜索的字符串，expression是被搜索的字符串。一般情况下expression是一个表中的一个字段，pattern的前后需要用“%”标记，除非你搜索的字符串在被收缩的字符串的最前面或者最后面。和CHARINDEX函数一样，PATINDEX函数返回搜索字符串在被搜索字符串中的起始位置。假如有这样一个PATINDEX函数：PATINDEX('%BC%','ABCD')这个PATINDEX函数返回的结果是2，这和CHARINDEX函数一样。这里的%标记告诉PATINDEX函数去找字符串“BC”，不管被搜索的字符串中在“BC”的前后有多少字符！假如你想知道被搜索字符串是否由特定的字符串开始，你可以省去前面的%标记。PATINDED函数就要这样写：PATINDEX('AB%','ABCD')这个命令执行的结果返回1，表示搜索的字符串“AB”在被搜索的字符串中“ABCD”被找到。使用通配符可以编辑比我以上举得简单例子复杂得多的搜索字符串。假如说你要确定一个字符串是否包含字母A和Z，还有任何数字，这个PARINDEX函数命令可能像这样：ATINDEX('%[A,Z,0-9]%[A,Z,0-9]%[A,Z,0-9]%','XYZABC123')注意在上面这个例子中的搜索字符部分使用了很多的通陪符。察看SQL Server联机丛书可以获得更多关于通佩符的信息。接下来，我们用两个例子来看PATINDEX和SELECT怎么联合起来使用。假设你想要找出Northwind.dbo.Categories表中Description字段中是包含单词“Bread”或“bread”的所有记录，那么选择语句就可能是这样：SELECT Description from Northwind.dbo.CategoriesWHERE patindex('%[b,B]read%',description) > 0这里我用通配符来确定大写和小写的“b”。我在Notthwind数据库中执行这个脚本后，得到下面的结果：Description--------------------------------------------------------Desserts, candies, and sweet breadsBreads, crackers, pasta, and cereal这是再用另外一个额外的通配符来查找一些记录的例子。这个例子是如何选出上面的查询结果中，Description字段的第二子字母不是“e”的纪录。select Description from Northwind.dbo.Categories where patindex('%[b,B]read%',description) > 0 and patindex('_[^e]%',description) = 1 通过在条件语句中增加一个使用^通配符的PATINDEX函数，我们可以过滤掉“Dessert, candies, and sweet breads”这条记录。上面的查询结果只有一条记录。Description--------------------------------------------------------Breads, crackers, pasta, and cereal （转摘）EXCEL 、OPENOFFICE CALC：SEARCH('目標字符串'，‘查詢字符串源’，起始位置):例如：SEARCH("B";"ABCDE";1)
阅读(5056) | 评论(0) | 转发(0) |
相关热门文章
给主人留下些什么吧！~~
请登录后评论。