1.什么是二分查找？
二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。 ----搜狗百科
2.二分查找的思想
二分查找的基本思想是将n个元素分成大致相等的两部分，取a[n/2]与x做比较，如果x=a[n/2],则找到x,算法中止；如果x<a[n/2],则只要在数组a的左半部分继续搜索x,如果x>a[n/2],则只要在数组a的右半部搜索x.
3.代码实现
public static int binarySearch(int []array,int a){ int lo=0; int hi=array.length-1; int mid; while(lo<=hi){ mid=(lo+hi)>>>1;//中间位置 if(array[mid]==a){ return mid+1; }else if(array[mid]<a){ //向右查找 lo=mid+1; }else{ //向左查找 hi=mid-1; } } return -1; }
敲黑板划重点：mid=(lo+hi)>>>1;对于这行代码里边的“>>>”这个无符号右移是考虑int类型溢出的这种场合，可以去参考java.util.Collections.binarySearch().然而在JDK1.5的时候埋藏了一个很久的bug（mid=(lo+hi)>>1），这里出现的“>>”（有符号右移），直到JDK1.6的时候才修复为“>>>”（无符号右移）。
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
