首页 > 代码库 > 《算法导论》习题2.3-5 二分搜索 Binary Search
《算法导论》习题2.3-5 二分搜索 Binary Search
地球人都知道“二分查找”，方法也非常简单，但是你能不能在10分钟内写出一个没有bug的程序呢？
知易行难，自己动手写一下试一试吧。
public class BinarySearch { public static int search(int [] A,int target,int a, int b) { int middle = (a+b)/2; if(a>b) return -1; else if (A[middle]==target) return middle; else if (A[middle]< target) return search(A,target,middle+1,b); else return search(A,target,a,middle-1); } public static void main(String[] args) { // TODO Auto-generated method stub int A [] = {2,4,6,8,10}; System.out.println( BinarySearch.search(A,1 , 0, A.length-1) ); System.out.println( BinarySearch.search(A,2 , 0, A.length-1) ); System.out.println( BinarySearch.search(A,3 , 0, A.length-1) ); System.out.println( BinarySearch.search(A,4 , 0, A.length-1) ); System.out.println( BinarySearch.search(A,5 , 0, A.length-1) ); System.out.println( BinarySearch.search(A,6 , 0, A.length-1) ); System.out.println( BinarySearch.search(A,7 , 0, A.length-1) ); System.out.println( BinarySearch.search(A,8 , 0, A.length-1) ); System.out.println( BinarySearch.search(A,9 , 0, A.length-1) ); System.out.println( BinarySearch.search(A,10 , 0, A.length-1) ); System.out.println( BinarySearch.search(A,11 , 0, A.length-1) ); }}
上面的代码看似是没有任何问题了，但是呢，其实还是有一个很微妙的bug，这个bug发生在：
int middle = (a+b)/2;
这一行。想一下，如果a+b超出了Int型的最大值了呢？？？
所以呢，修正这个bug应该这样：
public class BinarySearch { public static int search(int [] A,int target,int a, int b) { int middle = a+(b-a)/2; if(a>b) return -1; else if (A[middle]==target) return middle; else if (A[middle]< target) return search(A,target,middle+1,b); else return search(A,target,a,middle-1); } public static void main(String[] args) { // TODO Auto-generated method stub int A [] = {2,4,6,8,10}; System.out.println( BinarySearch.search(A,1 , 0, A.length-1) ); System.out.println( BinarySearch.search(A,2 , 0, A.length-1) ); System.out.println( BinarySearch.search(A,3 , 0, A.length-1) ); System.out.println( BinarySearch.search(A,4 , 0, A.length-1) ); System.out.println( BinarySearch.search(A,5 , 0, A.length-1) ); System.out.println( BinarySearch.search(A,6 , 0, A.length-1) ); System.out.println( BinarySearch.search(A,7 , 0, A.length-1) ); System.out.println( BinarySearch.search(A,8 , 0, A.length-1) ); System.out.println( BinarySearch.search(A,9 , 0, A.length-1) ); System.out.println( BinarySearch.search(A,10 , 0, A.length-1) ); System.out.println( BinarySearch.search(A,11 , 0, A.length-1) ); }}
The end......
《算法导论》习题2.3-5 二分搜索 Binary Search
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。