|
<span class="hljs-comment">// 使用递归实现的二分查找
<span class="hljs-keyword">private <span class="hljs-keyword">static<T extends Comparable> <span class="hljs-function"><span class="hljs-keyword">int <span class="hljs-title">binarySearch<span class="hljs-params">(T[] x,<span class="hljs-keyword">int low,<span class="hljs-keyword">int high,T key) {
<span class="hljs-keyword">if(low <= high) {
<span class="hljs-keyword">int mid = low + ((high - low) >> <span class="hljs-number">1);
<span class="hljs-keyword">if(key.compareTo(x[mid])== <span class="hljs-number">0) {
<span class="hljs-keyword">return mid;
}
<span class="hljs-keyword">else <span class="hljs-keyword">if(key.compareTo(x[mid])< <span class="hljs-number">0) {
<span class="hljs-keyword">return binarySearch(x,mid - <span class="hljs-number">1,key);
}
<span class="hljs-keyword">else {
<span class="hljs-keyword">return binarySearch(x,mid + <span class="hljs-number">1,key);
}
}
<span class="hljs-keyword">return -<span class="hljs-number">1;
}
}
<span class="cke_reset cke_widget_drag_handler_container"><img class="cke_reset cke_widget_drag_handler" title="点击并拖拽以移动" src="data:image/gif;base64,R0lGODlhAQABAPABAP///wAAACH5BAEKAAAALAAAAAABAAEAAAICRAEAOw==" alt="" width="15" height="15" data-cke-widget-drag-handler="1">
说明：上面的代码中给出了折半查找的两个版本，一个用递归实现，一个用循环实现。需要注意的是计算中间位置时不应该使用(high+ low) / 2的方式，因为加法运算可能导致整数越界，这里应该使用以下三种方式之一：low + (high - low) / 2或low + (high – low) >> 1或(low + high) >>> 1（>>>是逻辑右移，是不带符号位的右移）
（编辑：晋中站长网）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
|
