1.实践题目
7-1 二分查找 （20 分）
输入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
2.问题描述
要求对输入的数组运用二分查找法，从数组中查找给定的元素，查找成功则输出其所在位置及比较次数，否则输出-1及比较次数。
3.算法描述
运用二分查找法进行搜索
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n = input.nextInt();
int[] a = new int[10000];
for (int i = 0; i < n; i++) {
a[i] = input.nextInt();
}
int x = input.nextInt();
BinarySearch(a, x, n);
}
public static int BinarySearch(int a[], int x, int n) {
int left = 0;
int right = n - 1;
int count = 0;
while (left <= right) {
int middle = (left + right) / 2;
count++;
if (x == a[middle]) {
System.out.println(middle);
System.out.print(count);
return middle;
}
if (x > a[middle]) {
left = middle + 1;
} else {
right = middle - 1;
}
}
System.out.println("-1");
System.out.print(count);
return -1;
}
}
4.算法时间及空间复杂度分析
时间复杂度：该题运用了二分查找算法，即每执行一次while循环，待查找数组的长度减小一半，则时间复杂度为T(n) = O(logn)
空间复杂度：因为辅助空间是常数级别的，空间复杂度为O(1)
5.心得体会
本次实践完成了三道题，每一题都有各自的难点，在写算法的时候，应尽量优化算法，尽可能让时间复杂度小，学会优化算法；另外平时要多看书本上的例题，同时多做题，找到写算法的感觉。此次实践以小组方式进行，在合作过程中，彼此的交流能够更有效率完成题目，也促进了双方的进步，希望在以后实践讨论的过程中收获更多知识，不断成长。
原文：https://www.cnblogs.com/Daylight-Deng/p/11575736.html