算法第二章上机实践报告
组员:高珞洋,何汶珊
实践题目
7-2 改写二分搜索算法
设a[0:n-1]是已排好序的数组,请改写二分搜索算法,使得当x不在数组中时,返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时,i和j相同,均为x在数组中的位置。 输入有两行:第一行是n值和x值; 第二行是n个不相同的整数组成的非降序序列,每个整数之间以空格分隔。 输出格式:输出小于x的最大元素的最大下标i和大于x的最小元素的最小下标j。当搜索元素在数组中时,i和j相同。 提示:若x小于全部数值,则输出:-1 0 若x大于全部数值,则输出:n-1的值 n的值问题描述
这道题和平常的二分搜索不同的地方子在于不需要中位数,而是需要表示所找数在数列中左右两个数的位置(如果找到则这两个位置相同,即为所找数的位置)
较为繁琐的是需要考虑的临界情况增加了,当所找数小于或大于所有数的时候都要额外讨论。 但是在课后,我们考虑到,输出的数要么是一样的(找到),要么就差一(找不到),那么我是不是可以只用一个数来表示,这样就不用两个变量表示左右两个数的位置了 根据上述想法,有了以下代码算法描述
算法主体为biSearch方法,设置position这个全局变量作为最终结果
我们规定,找不到的时候用position和position + 1作为结果 那么首先要确定的是,找不到的情况下position的值应该是多少呢? 既然是position和position + 1,那么position的值应该是目标数左边的数的位置,即比较小的数的位置,再考虑到进入这个分支的条件是left > right 此时比较小的数是list[right], 那么,在找不到的这种情况下position的值应该是right 和基本的二分搜索不同的是,我们将二分搜索的找到的情况列出,放在递归调用前,作为停止递归调用的条件之一。 因为实际上只有一个变量position,而输出的时候有两种情况,找到(输出position和position)或者找不到(输出position和position + 1),区分这两种输出,我们额外设置一个全局变量isFound作为判断是否找到的标志,其值在找到或者找不到的方法里进行修改,方便修改isFound的值也是将找到的情况放在递归调用前的原因之一。 之后的递归调用不多说,若目标数大于中位数递归右半部分,小于中位数递归左半部分算法时间及空间复杂度
时间复杂度
单次调用的时间为O(1),因为实质上就只有判断找到、找不到、进行递归三种情况的语句(包括找到或找不到的执行语句)
根据递归调用,数组的长度是n,二分后是n/2,再二分后是n/4……直到二分到1结束(最坏情况) 那么假设二分的次数为Y,则有n*(1/2)^Y=1;Y = Logn.
最终时间复杂度有:(不算数组输入时间)
T(n) = Logn * O(1) = O(Logn)
空间复杂度
所定义的全局变量所产生的空间复杂度为O(1),更多的是递归调用所产生的空间
每次递归都会定义一个空间存放mid,空间复杂度为O(1),循环次数求得为Logn 最终空间复杂度有:(不算数组空间)S(n) =O(1) + Logn * O(1) = O(Logn)
心得体会
不要被题目的条件所限定。此题题目说明有两个参数“小于x的最大元素位置i和大于x的最小元素位置j”,一开始我们也是设置了两个全局变量保存这两个数,但是会让代码显得比较冗长。但是这两个值相互关联,因此可以只用一个值代替。
使用的语言本身会对程序的运行时间造成影响,比如C++ < Java,有时候运行超市,说不定不是算法的问题而是所用语言的问题。这体现了C语言追求性能,而Java追求效率源码
import java.util.Scanner;public class Main{ private static int position; private static boolean isFound; private static void biSearch(int[] list, int left, int right, int target, int n){ int mid = (left + right) / 2; //找不到 if (left > right) { position = right; isFound = false; return; } //找到了 if(list[mid] == target) { position = mid; isFound = true; return; } if(list[mid] < target) { //目标大于中位数 biSearch(list, mid + 1, right, target, n); } else { //目标小于中位数 biSearch(list, left, mid - 1, target, n); } } public static void main(String[] args) { Scanner input = new Scanner(System.in); int n = input.nextInt(); int target = input.nextInt(); int[] list = new int[n]; for (int i = 0; i < n; i++) { list[i] = input.nextInt(); } biSearch(list, 0, n - 1, target, n); if(!isFound) { System.out.println(position + " " + (position + 1)); } else { System.out.println(position + " " + position); } }}
posted on 2019-09-21 21:48 阅读( ...) 评论( ...) 收藏