1.实践题目：7-1 二分查找

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

3.算法描述：

将n个元素分成个数大致相同的两份，取a[n/2]与x比较。

若x==a[n/2],程序停止，输出下标，

若x<a[n/2]，在数组a的左半部查找x，

若x>a[n/2]，在数组a的右半部查找x，

若x不存在，输出-1

4.算法时间及空间复杂度分析

代码：

import java.util.Scanner;public class Main {		public static void main(String[] args) {			// TODO Auto-generated method stub			Scanner input = new Scanner(System.in);			int n = input.nextInt();			int [] list1 = new int[n];			for(int i=0;i
     
      right){			System.out.println(-1);			System.out.print(num);			}		}	}
     

　　在最坏情况下，while循环被执行了O(logn)次（2为底，下同），计数器num的时间负责度为O(1)。循环体内运算需要O(1)时间，所以整个算法在最坏情况下的计算时间复杂性为O(logn)。

因为没有使用递归，使用的空间都为常数级，所以空间复杂度为O(1)。

5.心得体会

一开始对于计数器num放在哪里是不确定的，后来跟搭档讨论后决定放在while里面判断之前，这样每次判断就属于比较一次，可以记录下比较次数。跟同学讨论，确实能比自己埋头苦想更快想出解决办法。