曾经研究过二分搜索的各种变种:
今天无意中看了下 JDK 中二分搜索的实现,确实很精巧,特别是返回插入点的设计很不错!用javascript实现下哦:
<script type="text/javascript">
/*
please sort first
如果找到返回查找值所在索引
否则返回-(x+1) (插入点 x : , -(x+1) 防止 x=0的插入点 与 找到的情况矛盾))
则判断某值是否存在只需判断 返回值 >=0 即可
*/
Array.prototype.binarySearch=function(v){
var l=0;
var h=this.length-1;
while(l<=h) {
//注:位操作javascript不一定提高效率
var m=(l+h)>>>1;
if(this[m]===v) {
return m;
}
if(this[m]>v) {
h=m-1;
} else {
l=m+1;
}
}
return -(l+1);
}
var t=[1,10,18,7,5,12,398,52];
t.sort(function(x,y){
return x-y;
});
alert("Array : "+t);
alert("Array : "+t+"\n"+"7 @index :"+t.binarySearch(7));
alert("Array : "+t+"\n"+"12 @index :"+t.binarySearch(12));
//重新计算得回 插入点
alert("Array : "+t+"\n"+"13 should insert :"+ (0-t.binarySearch(13)-1))
//fine ,let's insert
t.splice((0-t.binarySearch(13)-1),0,13);
alert("Array : "+t+"\n"+"now 13 @index :"+t.binarySearch(13));
</script>
分享到:
相关推荐
NULL 博文链接:https://128kj.iteye.com/blog/1747459
主要介绍了JAVA基于Arrays.sort()实现数组升序和降序,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下
个人研究所得,包含对其内部jdk源码的分析。 同时会结合ArrayList中对该两个方法的调用做进一步说明。...总结一句话:在允许的情况下,尽量调用System.arraycopy方法,实在不行再调用Arrays.copyOf方法。
Apress.PHP.Arrays.Single.Multi-dimensional.Associative.and.Object.Arrays.in.PHP.7.1484225554.rar 最新书籍,精讲PHP数组,文字版PDF
Arduino项目开发 Control_Arrays_Arrays.pdf Arduino项目开发 Control_Arrays_Arrays.pdf Arduino项目开发 Control_Arrays_Arrays.pdf Arduino项目开发 Control_Arrays_Arrays.pdf Arduino项目开发 Control_Arrays_...
主要介绍了Java Arrays.sort和Collections.sort排序实现原理解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
Gain an in-depth understanding of PHP 7 arrays. After a quick overview of PHP 7, each chapter concentrates on single, multi-dimensional, associative, and object arrays. PHP Arrays is a first of its ...
Antenna Arrays.pdf
本文主要对Arrays.asList方法进行总结。具有很好的参考价值,下面跟着小编一起来看下吧
网络图片地址url集合arrays.xml文件
Java Methods-Arrays.ppt
Introducing Structures and Cell Arrays.zip
15. JavaScript Functions, Objects, and Arrays 16. JavaScript and PHP Validation and Error Handling 17. Using Ajax 18. Introduction to CSS 19. Advanced CSS with CSS3 20. Accessing CSS from JavaScript ...
Calculate the mutual impedance in an infinite phased arrays.
数据结构严蔚敏chapter2arrays.ppt
Protein.Arrays,.Biochips,.and.Proteomics.-.Joanna.S.Albala
Arrays.asList、ArrayList的subList坑
C程序设计英文课件:CHAPTE 5 Pointer and Arrays.ppt
Introduction to Embedded System Design Using Field Programmable Gate Arrays. As the uses of digital systems continue to proliferate in quantity and variety, field programmable gate arrays (FPGAs) are ...
Java语言程序设计基础篇课后题答案-Chapter6Arrays.pdf