几种查找算法Java实现
2
/** * 类名:SearchTest.java * 说明: 几种查找方法 */ public class SearchTest { /** * 函数名称:binarySearch * 说明:二分查找 时间复杂度O(logN) */ //驱动例程 public static <AnyType extends Comparable<? super AnyType>> int binary(AnyType[] a,AnyType x){ return binary(a,0,a.length-1,x); } //递归 /* public static <AnyType extends Comparable<? super AnyType>> int binary(AnyType[] a,int low,int high,AnyType x){ if(low > high) return -1; int mid = (low + high)/2; if(a[mid].compareTo(x) > 0 ) return binary(a,low,mid - 1,x); else if(a[mid].compareTo(x) < 0 ) return binary(a,mid+1,high,x); else return mid; }*/ //非递归 public static <AnyType extends Comparable<? super AnyType>> int binary(AnyType[] a,int low,int high,AnyType x){ while(low <= high){ int mid = (low + high)/2; if(a[mid].compareTo(x) > 0) high = mid -1; else if(a[mid].compareTo(x) < 0) low = mid + 1; else return mid; } return -1; } /** * 函数名称:main * 说明:测试 */ public static void main(String[] args) { // TODO 自动生成的方法存根 Integer[] a = new Integer[]{1,2,3,4,5,6}; int x = 3; System.out.println(binary(a,x)); } }