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. 心得体会
本次实践完成了三道题, 每一题都有各自的难点, 在写算法的时候, 应尽量优化算法, 尽可能让时间复杂度小, 学会优化算法; 另外平时要多看书本上的例题, 同时多做题, 找到写算法的感觉. 此次实践以小组方式进行, 在合作过程中, 彼此的交流能够更有效率完成题目, 也促进了双方的进步, 希望在以后实践讨论的过程中收获更多知识, 不断成长.
来源: http://www.bubuko.com/infodetail-3210579.html