二分法查找数组是否包含某一元素_PHP教程
- WBOY原創
- 2016-07-20 11:13:46780瀏覽
二分法查找数组是否包含某一元素，兼容正反序，代码实现：
<span 1</span> <?<span php
</span><span 2</span>
<span 3</span> <span $searchValue</span> = (int)<span $_GET</span>['key'<span ];
</span><span 4</span>
<span 5</span> <span function</span> search(<span array</span> <span $array</span>, <span $value</span><span )
</span><span 6</span> <span {
</span><span 7</span> <span $max</span> = <span count</span>(<span $array</span>)-1<span ;
</span><span 8</span> <span $min</span> = 0<span ;
</span><span 9</span> <span $isAscSort</span> = <span $array</span>[<span $min</span>] < <span $array</span>[<span $max</span><span ];
</span><span 10</span>
<span 11</span> <span while</span> (<span TRUE</span><span ) {
</span><span 12</span> <span $sum</span> = <span $min</span>+<span $max</span><span ;
</span><span 13</span> <span $midKey</span> = (int)(<span $sum</span>%2 == 1 ? <span ceil</span>(<span $sum</span>/2) : <span $sum</span>/2<span );
</span><span 14</span>
<span 15</span> <span if</span> (<span $max</span> < <span $min</span><span ) {
</span><span 16</span> <span return</span> -1<span ;
</span><span 17</span> } <span else</span> <span if</span> (<span $value</span> == <span $array</span>[<span $midKey</span><span ]) {
</span><span 18</span> <span return</span> 1<span ;
</span><span 19</span> } <span else</span> <span if</span> (<span $value</span> > <span $array</span>[<span $midKey</span><span ]) {
</span><span 20</span> <span $isAscSort</span> ? <span $min</span> = <span $midKey</span>+1 : <span $max</span> = <span $midKey</span>-1<span ;
</span><span 21</span> } <span else</span> <span if</span> (<span $value</span> < <span $array</span>[<span $midKey</span><span ]) {
</span><span 22</span> <span $isAscSort</span> ? <span $max</span> = <span $midKey</span>-1 : <span $min</span> = <span $midKey</span>+1<span ;
</span><span 23</span> <span }
</span><span 24</span> <span }
</span><span 25</span> <span }
</span><span 26</span>
<span 27</span> <span $array</span> = <span array</span><span (
</span><span 28</span> '4', '5', '7', '8', '9', '10', '11', '12'
<span 29</span> <span );
</span><span 30</span> <span //</span><span 正序</span>
<span 31</span> <span echo</span> search(<span $array</span>, <span $searchValue</span><span );
</span><span 32</span>
<span 33</span> <span //</span><span 逆序</span>
<span 34</span> <span rsort</span>(<span $array</span><span );
</span><span 35</span> <span echo</span> search(<span $array</span>, <span $searchValue</span>);
这个没考虑非顺序键的数组，主要是方法，如果需要大家可以自己扩展下。
陳述：
本文內容由網友自願投稿，版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容，請聯絡admin@php.cn