22 lines
3.9 KiB
Text
22 lines
3.9 KiB
Text
-->
|
|
<span style="color: #008080;">global</span> <span style="color: #008080;">function</span> <span style="color: #7060A8;">binary_search</span><span style="color: #0000FF;">(</span><span style="color: #004080;">object</span> <span style="color: #000000;">needle</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">haystack</span><span style="color: #0000FF;">)</span>
|
|
<span style="color: #004080;">integer</span> <span style="color: #000000;">lo</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span>
|
|
<span style="color: #000000;">hi</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">haystack</span><span style="color: #0000FF;">),</span>
|
|
<span style="color: #000000;">mid</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">lo</span><span style="color: #0000FF;">,</span>
|
|
<span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
|
|
|
|
<span style="color: #008080;">while</span> <span style="color: #000000;">lo</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">hi</span> <span style="color: #008080;">do</span>
|
|
<span style="color: #000000;">mid</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">((</span><span style="color: #000000;">lo</span><span style="color: #0000FF;">+</span><span style="color: #000000;">hi</span><span style="color: #0000FF;">)/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
|
|
<span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">compare</span><span style="color: #0000FF;">(</span><span style="color: #000000;">needle</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">haystack</span><span style="color: #0000FF;">[</span><span style="color: #000000;">mid</span><span style="color: #0000FF;">])</span>
|
|
<span style="color: #008080;">if</span> <span style="color: #000000;">c</span><span style="color: #0000FF;"><</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
|
|
<span style="color: #000000;">hi</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">mid</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span>
|
|
<span style="color: #008080;">elsif</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">></span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
|
|
<span style="color: #000000;">lo</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">mid</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span>
|
|
<span style="color: #008080;">else</span>
|
|
<span style="color: #008080;">return</span> <span style="color: #000000;">mid</span> <span style="color: #000080;font-style:italic;">-- found!</span>
|
|
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
|
|
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
|
|
<span style="color: #000000;">mid</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">></span><span style="color: #000000;">0</span>
|
|
<span style="color: #008080;">return</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">mid</span> <span style="color: #000080;font-style:italic;">-- where it would go, if inserted now</span>
|
|
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
|
|
<!--
|