Java算法——二分查找及代码实现

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

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;
}

@Test
public void test3(){
    //查找（或搜索）
    //线性查找：

    //二分查找
    int[] arr2=new int[]{-98,-23,2,34,45,56,67,78,79,88,89,99,111,234,345,456,567,678,789};

    int dest=98;
    int head=0;
    int end=arr2.length-1;
    boolean Flag=true;
    while(head<=end){
        int middle=(head+end)/2;
        if(dest==arr2[middle]){
            System.out.println("we find it");
            Flag=false;
            break;
        }else if(arr2[middle]>dest){
            end=middle-1;
        }else{
            head=middle+1;
        }
    }
    if(Flag){
        System.out.println("no");
    }
}