算法导论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];
			//二分查找temp
			result = search(s,1,s.length-1,temp);
			if(result>=0)
				break;
		}
		if(result<0)
			return null;
		else
			return 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;
			else
				return -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;
	}
	
}

 

评论

2 楼 panggezi 2011-11-20  

现在面试都考O(N)的实现了。

1 楼 panggezi 2011-11-20  

现在面试都考O(N)的实现了。