search.java

<算法导论>第二版大部分算法实现. 1. 各类排序和顺序统计学相关 2. 数据结构 2.1 基本数据结构 2.2 散列表 2.3 二叉查找树 2.4 红黑树 2.5 数据结构

/*
 * Copyright (C) 2000-2007 Wang Pengcheng <[e-mail]>
 * Licensed to the Wang Pengcheng under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The LGPL licenses this file to You under the GNU Lesser General Public
 * Licence, Version 2.0  (the "License"); you may not use this file except in
 * compliance with the License.  You may obtain a copy of the License at
 *
 *     http://www.gnu.org/licenses/lgpl.txt
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

/**
 *
 *
 *
 */
 package cn.edu.whu.iss.algorithm.unit02;
 import mypackage.tools.print.P;
 
 public class Search{
 	
 	/**
 	 *Normal search perform the out of order elements
 	 *
 	 */
 	public static <Type extends Comparable> int normalSearch(Type element[],Type key){
 		for(int j=0;j<element.length;j++){
 			if(element[j].equals(key)){
 				return j;
 			}
 		}
 		return -(element.length);
 	}
 
 	/**
 	 *Binary search perform the order elements
 	 *
 	 */
 	public static <Type extends Comparable> int binarySearch(Type element[],Type key){
 		int l	=	0;
 		int r	=	element.length-1;
 		int mid	=	0;
 		while(l<=r){
 			mid	=	(l+r)>>1;//(l+r)/2
 			if(key.compareTo(element[mid])<0){
 				r	=	mid-1;
 			}else if(key.compareTo(element[mid])>0){
 				l	=	mid+1;
 			}else{
 				return mid;
 			}
 		}
 		return -mid-1;
 	}
 	
  	/**
 	 *Binary Recurrence search perform of order elements
 	 *
 	 */
 	public static <Type extends Comparable> int binarySearchRecurrence(Type element[],Type key,int l,int r){
 		int mid=(l+r)>>1;
 		if(l>r)return -mid-1;
 		if(key.compareTo(element[mid])<0){
 			return binarySearchRecurrence(element,key,l,mid-1);
 		}else if(key.compareTo(element[mid])>0){
 			return binarySearchRecurrence(element,key,mid+1,r);
 		}else {
 			return mid;
 		}
 	}
 	
 	public static void main(String[] args){
 		Integer[] a = new Integer[50];
 		//int[] a = new int[50];
 		for(int i=0;i<a.length;i++){
 			a[i]=i;
 		}
 		for(int i=0;i<a.length;i++){
 			P.rint(Search.normalSearch(a,a.length-i));
 			P.rint(" "+Search.binarySearch(a,a.length-i));
 			P.rintln(" "+Search.binarySearchRecurrence(a,a.length-i,0,a.length-1));
 		}
 	}
 }