二分法查找数组是否包含某一元素

二分法查找数组是否包含某一元素_PHP教程

WBOY

Lepaskan： 2016-07-20 11:13:46

asal

833 orang telah melayarinya

二分法查找数组是否包含某一元素，兼容正反序，代码实现：

<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>);

Salin selepas log masuk

这个没考虑非顺序键的数组，主要是方法，如果需要大家可以自己扩展下。