算法分析与设计实验报告

——二分搜索程序算法的实现

1.理解分治算法的概念和基本要素； 2.理解递归的概念； 3.掌握设计有效算法的分治策略； 4.通过二分搜索技术学习分治策略设计技巧；

操作系统：Windows 10 操作系统 开发工具：Eclipse(4.15.0) 开发语言：Java

1.使用二分搜索算法查找有序数列中的指定元素； 2.通过上机实验进行算法实现； 3.保存和打印出程序的运行结果，并结合程序进行分析，上交实验报告。

实验步骤：

问题1：编写递归方法时返回的边界错误，导致陷入死循环。如 return RecursionBinarySearch(arr,key,left,middle);//搜索左半区 return RecursionBinarySearch(arr,key,middle,right);//搜索右半区

正确修改：return RecursionBinarySearch(arr,key,left,middle-1); return RecursionBinarySearch(arr,key,middle+1,right);

问题2：编写迭代方法时while()的条件写成while(left //递归 if((keyarr[right])||(right>right))) return -1; int middle =(left &right) + ((left ^ right) >> 1); //防溢出(left &right) + ((left ^ right) >> 1); if(key return RecursionBinarySearch(arr,key,middle+1,right);//搜索右半区 } else { return middle; } } public static int CommonBinarySearch(int[] arr,int key) { //迭代 int left = 0; int right = arr.length-1; int middle = 0; if((keyarr[right])) return -1; while(left//选择排序 for(int i=0;i if(arr[j] Scanner sc = new Scanner(System.in); System.out.println("输入元素个数："); int n = sc.nextInt(); int position; int[] arr = new int[n];//输入数组元素 for(int i=0;i System.out.print(arr[i]+" "); } System.out.println(""); do { System.out.println("输入查找元素key："); int key =sc.nextInt(); //递归搜索 position = RecursionBinarySearch(arr,key,0,arr.length-1); if(position==-1) { System.out.println("查找"+key+",有序列中不存在"); } else { System.out.println("查找"+key+"（递归）\n"+"在有序列中的位置为："+position); } //迭代搜索 position = CommonBinarySearch(arr,key); if(position==-1) { System.out.println("查找"+key+",有序列中不存在"); } else { System.out.println("查找"+key+"(迭代)\n"+"在有序列中的位置为："+position); } }while(true); } }