算法导论Java实现-二分查找（习题2.3-5）

1. package lhz.algorithm.chapter.two; 
2.  
3. /** 
4.  * 二分查找，《算法导论》，习题2.3-5 
5.  *   Referring back to the searching problem (see Exercise 2.1-3), observe that if 
6.  * the sequence A is sorted, we can check the midpoint of the sequence against v 
7.  * and eliminate half of the sequence from further consideration. Binary search 
8.  * is an algorithm that repeats this procedure, halving the size of the 
9.  * remaining portion of the sequence each time. Write pseudocode, either 
10.  * iterative or recursive, for binary search. Argue that the worst-case running 
11.  * time of binary search is Θ(lg n). 
12.  * 附：习题2.1-3 
13.  *  Consider the searching problem:  
14.  * • Input: A sequence of n numbers A = a1, a2, . . . , an and a value v.  
15.  * • Output: An index i such that v = A[i] or the special value NIL if v does not appear in A.  
16.  * Write pseudocode for linear search, which scans through the sequence, looking for v.  
17.  * Using a loop invariant, prove that your algorithm is correct. Make sure that your loop 
18.  * invariant fulfills the three necessary properties. 
19.  * 本文地址：http://mushiqianmeng.blog.51cto.com/3970029/731203
20.  * @author lihzh(苦逼coder) 
21.  */ 
22. public class BinarySearch { 
23.      
24.     public static void main(String[] args) { 
25.         //根据题意，给定一个已经排好序的数组 
26.         int[] input = new int[]{1,2,3,4,5,6,7,8,9,10,11,12,13}; 
27.         //给定查找目标 
28.         int target = 6; 
29.         //初始从0到数组最后以后一位为范围 
30.         String result = binarySearch(input,target,0,input.length-1); 
31.         //打印输出 
32.         System.out.println(result); 
33.     } 
34.      
35.     /** 
36.      * 二分查找 
37.      * @param input 给定已排序的待查数组 
38.      * @param target 查找目标 
39.      * @param from 当前查找的范围起点 
40.      * @param to 当前查找的返回终点 
41.      * @return 返回目标在数组中的索引位置。如果不在数组中返回：NIL 
42.      */ 
43.     private static String binarySearch(int[] input, int target, int from, int to) { 
44.         int range = to - from; 
45.         //如果范围大于0，即存在两个以上的元素，则继续拆分 
46.         if (range > 0) { 
47.             //选定中间位 
48.             int mid = (to + from) / 2; 
49.             //先判断两个二分的临界位 
50.             if (input[mid] == target) { 
51.                 return String.valueOf(mid); 
52.             } 
53.             //如果临界位不满足，则继续二分查找 
54.             if (input[mid] > target) { 
55.                 return binarySearch(input,target,from,mid-1); 
56.             } else { 
57.                 return binarySearch(input,target,mid+1,to); 
58.             } 
59.         } else { 
60.             if (input[from] == target) { 
61.                 return String.valueOf(from); 
62.             } else { 
63.                 return "NIL"; 
64.             } 
65.         } 
66.         /* 
67.          * 复杂度分析： 
68.          * 在最坏情况下，一共要进行lgn次二分，可以确定最后结果。而每次二分中只进行二分和值的比较 
69.          * 等时间为常量的操作。因此，二分查找的时间复杂度为：Θ(lg n) 
70.          * 公式表示如下： 
71.          * 设数组长度是n的时候，时间为T(n)，则如果拆分成n/2长度的数组的时候，需要的时间为T(n/2)，切 
72.          * 无需合并，拆分需要时间为c，为常量。所以T(n)=T(n/2)+c，T(n/2)=T(n/4)+c... 
73.          * 所以，T(n)=c+c+c+...，攻击lgn个c。所以时间复杂副为：Θ(lg n) 
74.          */ 
75.     } 
76.  
77. } 

     本文转自mushiqianmeng 51CTO博客，原文链接：http://blog.51cto.com/mushiqianmeng/731203，如需转载请自行联系原作者