18、二分查找——java数据结构

18、二分查找

输入n值(1<=n<=1000)、n个非降序排列的整数以及要查找的数x，使用二分查找算法查找x，输出x所在的下标（0~n-1）及比较次数。若x不存在，输出-1和比较次数。

输入格式:
输入共三行： 第一行是n值； 第二行是n个整数； 第三行是x值。

输出格式:
输出x所在的下标（0~n-1）及比较次数。若x不存在，输出-1和比较次数。

输入样例:
4
1 2 3 4
1
输出样例:
0
2

代码如下：

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int time=0;
    public static int binSearch(int[] data, int key){
        int low=0,high=data.length-1,mid;
        while (high>=low) {
            time++;
            mid = (low + high) / 2;
            if (key == data[mid]) {
                return mid;
            } else if (key > data[mid]){
                low = mid + 1;
            }
            else {
                high = mid - 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int num=input.nextInt();
        int[]data=new int[num];
        for (int i=0;i<num;i++){
            int e=input.nextInt();
            data[i]=e;
        }
        Arrays.sort(data);
        int t=input.nextInt();
        System.out.println(binSearch(data,t));
        System.out.println(time);
    }
}