二分查找

佚名 6年前 (2019-04-08) 算法 1752人围观抢沙发百度已收录

1.什么是二分查找？

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。-----------搜狗百科

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

2.二分查找的思想

二分查找的基本思想是将n个元素分成大致相等的两部分，取a[n/2]与x做比较，如果x=a[n/2],则找到x,算法中止；如果x<a[n/2],则只要在数组a的左半部分继续搜索x,如果x>a[n/2],则只要在数组a的右半部搜索x.

3.代码实现

 1     public static int biSearch(int []array,int a){
 2         int lo=0;
 3         int hi=array.length-1;
 4         int mid;
 5         while(lo<=hi){
 6             mid=(lo+hi)>>>1;//中间位置
 7             if(array[mid]==a){
 8                 return mid+1;
 9             }else if(array[mid]<a){ //向右查找
10                 lo=mid+1;
11             }else{ //向左查找
12                 hi=mid-1;
13             }
14         }
15         return -1;
16     
17     }