java实现二分查找

算法思想：又叫折半查找，要求待查找的序列有序。每次取中间位置的值与待查关键字比较，如果中间位置的值比待查关键字大，则在前半部分循环这个查找的过程，如果中间位置的值比待查关键字小，则在后半部分循环这个查找的过程。直到查找到了为止，否则序列中没有待查的关键字。

1.非递归实现：

public static int biSearch(int []array,int a){         int lo=0;         int hi=array.length-1;         int mid;         while(lo<=hi){             mid=(lo+hi)/2;             if(array[mid]==a){                 return mid+1;             }else if(array[mid]<a){                 lo=mid+1;             }else{                 hi=mid-1;             }         }         return -1;     }

2.递归实现:

public static int sort(int []array,int a,int lo,int hi){         if(lo<=hi){             int mid=(lo+hi)/2;             if(a==array[mid]){                 return mid+1;             }             else if(a>array[mid]){                 return sort(array,a,mid+1,hi);             }else{                 return sort(array,a,lo,mid-1);             }         }         return -1;     }

3.查找第一个元素出现的位置(可能有重复的)：

public static int biSearch(int []array,int a){         int n=array.length;         int low=0;         int hi=n-1;         int mid=0;         while(low<hi){             mid=(low+hi)/2;             if(array[mid]<a){                 low=mid+1;             }else{                 hi=mid;             }         }         if(array[low]!=a){             return -1;         }else{             return low;         }     }

4.查询元素最后出现的位置:

public static int biSearch(int []array,int a){         int n=array.length;         int low=0;         int hi=n-1;         int mid=0;         while(low<hi){             mid=(low+hi+1)/2;             if(array[mid]<=a){                 low=mid;             }else{                 hi=mid-1;             }         }              if(array[low]!=a){             return -1;         }else{             return hi;         }     }