二分查找 代码 在有序数组里查找目标

APPLEUFO

主要看下面那段02   网上有模版写好的

  

窗口程序集名	保 留	保 留	备 注
程序集1

子程序名	返回值类型	公开	备 注
子程序_二分查找	逻辑型		自己写的   真 找到，   假 没有
参数名	类 型	参考	可空	数组	备 注
参数_寻找者	文本型
参数_被寻找文本数组	文本型				排序过的

变量名	类 型	静态	数组	备 注
局变_开始	整数型
局变_结束	整数型
局变_中间	整数型

局变_开始 ＝ 1
局变_结束 ＝ 取数组成员数 (参数_被寻找文本数组) ＋ 1
局变_中间 ＝ 局变_结束 ÷ 2
循环判断首 ()
如果 (参数_寻找者 ＝ 参数_被寻找文本数组 [局变_中间])
返回 (真)


如果 (局变_开始 ＝ 局变_结束)  ' 看看要不要加 大于
跳出循环 ()


' 无动作

如果 (参数_寻找者 ＜ 参数_被寻找文本数组 [局变_中间])  ' '  否则就是大于
局变_结束 ＝ 局变_中间 － 1


局变_开始 ＝ 局变_中间 ＋ 1

局变_中间 ＝ (局变_开始 ＋ 局变_结束) ÷ 2
如果真 (局变_中间 ＞ 取数组成员数 (参数_被寻找文本数组))
跳出循环 ()


循环判断尾 (真)
返回 (假)

子程序名	返回值类型	公开	备 注
子程序_二分查找02	整数型		0 没有   其他 找到
参数名	类 型	参考	可空	数组	备 注
参数_寻找者	文本型
参数_被寻找文本数组	文本型				排序过的

变量名	类 型	静态	数组	备 注
局变_开始	整数型
局变_结束	整数型
局变_中间	整数型

局变_开始 ＝ 1
局变_结束 ＝ 取数组成员数 (参数_被寻找文本数组)
判断循环首 (局变_开始 ≤ 局变_结束)
' 局变_中间 ＝ (局变_开始 ＋ 局变_结束) ÷ 2
局变_中间 ＝ 局变_开始 ��� (局变_结束 － 局变_开始) ÷ 2  ' 原本是上面这样，为了防止大数相加 整数型溢出改的
如果 (参数_寻找者 ＝ 参数_被寻找文本数组 [局变_中间])
返回 (局变_中间)


如果 (参数_寻找者 ＜ 参数_被寻找文本数组 [局变_中间])  ' '  否则就是大于
局变_结束 ＝ 局变_中间 － 1


局变_开始 ＝ 局变_中间 ＋ 1


判断循环尾 ()
返回 (0)
' ' 网上抄的         https://my.oschina.net/lht007/blog/4705655   来源
' 3、简单的二分查找   ' 简单的二分查找我想大家应该都写过。但是想一次将二分查找写对估计 10 个人里面只有 1 个人能做到。下面给出题目和代码，我们具体来分析一下。
' 题目：在有序的数组a里，找到某个指定的数据value。
' public int bsearch($a, $value) {
' int $low = 0;
' int $high = $a.length - 1;
' while ($low <= $high) {
' int $mid = ($low + $high) / 2;
' if ($a[mid] == $value) {
' return $mid;
' } else if ($a[mid] < $value) {
' $low = $mid + 1;
' } else {
' $high = $mid - 1;
' }
' }
' return -1;
' }
' 上诉代码可以作为一个二分查找的模板代码，我相信你能轻易的看懂这段代码。这里需要强调几个容易出错的地方：
' 1. 循环退出条件：
' 注意是 $low<=$high，而不是 $low
' 2.mid 的取值：
' 实际上，$mid=($low+$high)/2 这种写法是有问题的。因为如果 $low 和 $high 比较大的话，两者之和就有可能会溢出。改进的方法是将 $mid 的计算方式写成 $low+($high-$low)/2。更进一步，如果要将性能优化到极致的话，我们可以将这里的除以 2 操作转化成位运算 $low+(($high-$low)>>1)。因为相比除法运算来说，计算机处理位运算要快得多。
' 3.low 和 high 的更新
' $low=$mid+1，$high=$mid-1。注意这里的 +1 和 -1，如果直接写成 $low=$mid 或者 $high=$mid，就可能会发生死循环。比如，当 $high=3，$low=3 时，如果 a [3] 不等于 value，就会导致一直循环不退出。

.版本 2<br /> <br /> .程序集 程序集1<br /> <br /> .子程序 子程序_二分查找, 逻辑型, 公开,     自己写的   真 找到，   假 没有<br /> .参数 参数_寻找者, 文本型<br /> .参数 参数_被寻找文本数组, 文本型, 数组,  排序过的<br /> .局部变量 局变_开始, 整数型<br /> .局部变量 局变_结束, 整数型<br /> .局部变量 局变_中间, 整数型<br /> <br /> 局变_开始 ＝ 1<br /> 局变_结束 ＝ 取数组成员数 (参数_被寻找文本数组) ＋ 1<br /> 局变_中间 ＝ 局变_结束 ÷ 2<br /> <br /> .循环判断首 ()<br /> <br />     .如果 (参数_寻找者 ＝ 参数_被寻找文本数组 [局变_中间])<br />         返回 (真)<br />     .否则<br /> <br /> <br />         .如果 (局变_开始 ＝ 局变_结束)  ' 看看要不要加 大于<br />             跳出循环 ()<br />         .否则<br /> <br />             ' 无动作<br />         .如果结束<br /> <br />         .如果 (参数_寻找者 ＜ 参数_被寻找文本数组 [局变_中间])  ' '  否则就是大于<br /> <br />             局变_结束 ＝ 局变_中间 － 1<br />         .否则<br /> <br />             局变_开始 ＝ 局变_中间 ＋ 1<br />         .如果结束<br /> <br />         局变_中间 ＝ (局变_开始 ＋ 局变_结束) ÷ 2<br /> <br />         .如果真 (局变_中间 ＞ 取数组成员数 (参数_被寻找文本数组))<br />             跳出循环 ()<br />         .如果真结束<br /> <br />     .如果结束<br /> <br /> .循环判断尾 (真)<br /> <br /> 返回 (假)<br /> <br /> <br /> <br /> .子程序 子程序_二分查找02, 整数型, 公开,  0 没有   其他 找到    <br /> .参数 参数_寻找者, 文本型<br /> .参数 参数_被寻找文本数组, 文本型, 数组,  排序过的<br /> .局部变量 局变_开始, 整数型<br /> .局部变量 局变_结束, 整数型<br /> .局部变量 局变_中间, 整数型<br /> <br /> 局变_开始 ＝ 1<br /> 局变_结束 ＝ 取数组成员数 (参数_被寻找文本数组)<br /> <br /> .判断循环首 (局变_开始 ≤ 局变_结束)<br /> <br />     ' 局变_中间 ＝ (局变_开始 ＋ 局变_结束) ÷ 2<br />     局变_中间 ＝ 局变_开始 ＋ (局变_结束 － 局变_开始) ÷ 2  ' 原本是上面这样，为了防止大数相加 整数型溢出改的<br /> <br />     .如果 (参数_寻找者 ＝ 参数_被寻找文本数组 [局变_中间])<br />         返回 (局变_中间)<br />     .否则<br /> <br />         .如果 (参数_寻找者 ＜ 参数_被寻找文本数组 [局变_中间])  ' '  否则就是大于<br /> <br />             局变_结束 ＝ 局变_中间 － 1<br />         .否则<br /> <br />             局变_开始 ＝ 局变_中间 ＋ 1<br />         .如果结束<br /> <br />     .如果结束<br /> <br /> .判断循环尾 ()<br /> <br /> 返回 (0)<br /> <br /> ' ' 网上抄的         https://my.oschina.net/lht007/blog/4705655   来源<br /> ' 3、简单的二分查找   ' 简单的二分查找我想大家应该都写过。但是想一次将二分查找写对估计 10 个人里面只有 1 个人能做到。下面给出题目和代码，我们具体来分析一下。<br /> ' 题目：在有序的数组a里，找到某个指定的数据value。<br /> ' public int bsearch($a, $value) {<br /> ' int $low = 0;<br /> ' int $high = $a.length - 1;<br /> <br /> ' while ($low <= $high) {<br /> ' int $mid = ($low + $high) / 2;<br /> ' if ($a[mid] == $value) {<br /> ' return $mid;<br /> ' } else if ($a[mid] < $value) {<br /> ' $low = $mid + 1;<br /> ' } else {<br /> ' $high = $mid - 1;<br /> ' }<br /> ' }<br /> <br /> ' return -1;<br /> ' }<br /> ' 上诉代码可以作为一个二分查找的模板代码，我相信你能轻易的看懂这段代码。这里需要强调几个容易出错的地方：<br /> <br /> ' 1. 循环退出条件：<br /> <br /> ' 注意是 $low<=$high，而不是 $low<br /> <br /> ' 2.mid 的取值：<br /> <br /> ' 实际上，$mid=($low+$high)/2 这种写法是有问题的。因为如果 $low 和 $high 比较大的话，两者之和就有可能会溢出。改进的方法是将 $mid 的计算方式写成 $low+($high-$low)/2。更进一步，如果要将性能优化到极致的话，我们可以将这里的除以 2 操作转化成位运算 $low+(($high-$low)>>1)。因为相比除法运算来说，计算机处理位运算要快得多。<br /> <br /> ' 3.low 和 high 的更新<br /> <br /> ' $low=$mid+1，$high=$mid-1。注意这里的 +1 和 -1，如果直接写成 $low=$mid 或者 $high=$mid，就可能会发生死循环。比如，当 $high=3，$low=3 时，如果 a [3] 不等于 value，就会导致一直循环不退出。

笨来无一悟

功德无量

pipicool

学习一下

光影魔术

感谢分享源码

杨明煜

学习进步！......

豆豆灰常开心

全都是大佬~

查过

感谢发布原创作品，精易因你更精彩！6666666666666

胖子葛格

感谢大神分享~！

447485268

支持开源~！感谢分享

zaozi

感谢您对论坛的支持