算法导论2.3-7 二分查找变种题目

package Chapter2;/* * 题目：算法导论2.3.7 * 请给出一个运行时间为O（nlgn）的算法，使之能在给定一个由n个整数构成的集合S和另一个整数x时， * 判断出S中是否存在有两个其和等于S的数 *  *算法思想： *1、默认集合S是排序过的，若果没有排序，先排序。。。各种排序方法。 *2、本问题是二分查找的变形。。 *  for i ←1to n *     temp=x-array[i] *   二分查找temp * */public class SearchSum {public static void main(String args[]){int[]s={1,3,6,9,45,68,106};int x=9;Index index = new SearchSum().getFittedIndex(s, x);if(null==index)System.out.println("can't find");else{System.out.println("index_1: "+index.getIndex_1());System.out.println("index_2: "+index.getIndex_2());}}public Index getFittedIndex(int []s,int x){int result=-1;int i;for( i=0;i<s.length-1;i++){int temp=x-s[i];//二分查找tempresult = search(s,1,s.length-1,temp);if(result>=0)break;}if(result<0)return null;elsereturn new Index(i,result);}public static int search(int[] array,int start,int end,int target){int middle = (start+end)/2;if(target==array[middle])return middle;/* * 当数列只剩两个元素时{start,end} * 由于middle每次都等于start，故做特殊判断 *  */if(end==start+1)if(target==array[end])return end;elsereturn -1;if(target<array[middle])return search(array,start,middle,target);if(target>array[middle])return search(array,middle,end,target);return -1;}}class Index {private int index_1;private int index_2;public int getIndex_2() {return index_2;}public void setIndex_2(int index_2) {this.index_2 = index_2;}public int getIndex_1() {return index_1;}public void setIndex_1(int index_1) {this.index_1 = index_1;}public Index(int index_1, int index_2) {super();this.index_1 = index_1;this.index_2 = index_2;}}

?

1 楼 panggezi 2011-11-20 现在面试都考O(N)的实现了。 2 楼 panggezi 2011-11-20 现在面试都考O(N)的实现了。