算法之二分查找(java版实现加测试)

进阶版入口 递归处理的核心算法(加入·deep是为理解算法):

import edu.princeton.cs.algs4.*; public class Main{ public static int rank(int key,int[] a) { int deep = 0; return rank(key,a,0,a.length - 1,deep); } public static int rank(int key,int[] a,int lo,int hi,int deep) { if(lo > hi) return -1; int mid = lo + (hi - lo) / 2; if(a[mid] > key) { StdOut.printf("deep: %d lo: %d hi: %d\n",deep,lo,hi); ++deep; return rank(key,a,lo,mid - 1,deep); } else if(a[mid] < key) { StdOut.printf("deep: %d lo: %d hi: %d\n",deep,lo,hi); ++deep; return rank(key,a,mid + 1,hi,deep); } else { StdOut.printf("deep: %d lo: %d hi: %d\n",deep,lo,hi); return mid; } } public static void main(String[] args) { int M = 10; int[] a = new int[M]; for(int i = 0; i < M; ++i) a[i] = i; StdOut.printf("%d",rank(9,a)); } }

递归形式的测试:

public static void test(String mode,String file) { In in = new In(file); int[] a = in.readAllInts(); Arrays.sort(a); //"+"打印出不在白名单中的数 if(mode == "+") { while(!StdIn.isEmpty()) { int key = StdIn.readInt(); if(rank(key,a) == -1) { StdOut.printf("%d is not in whitelist\n", key); } } } //"-"打印出在白名单中的数 if(mode == "-") { while(!StdIn.isEmpty()) { int key = StdIn.readInt(); if(rank(key,a) != -1) StdOut.printf("%d is in whitelist\n",key); } } }

main:

public static void main(String[] args) { test("-","test.txt"); }

非递归核心算法:

public static int rank(int key,int[] a) { int lo = 0; int hi = a.length - 1; while(lo <= hi) { int mid = lo + (hi - lo) / 2; if(a[mid] > key) hi = mid - 1; else if(a[mid] < key) lo = mid + 1; else return mid; } return -1; }

非递归二分查找的测试:

public static void test(String mode,String file) { In in = new In(file); int[] a = in.readAllInts(); Arrays.sort(a); //"+"打印出不在白名单中的数 if(mode == "+") { while(!StdIn.isEmpty()) { int key = StdIn.readInt(); if(rank(key,a) == -1) { StdOut.printf("%d is not in whitelist\n", key); } } } //"-"打印出在白名单中的数 if(mode == "-") { while(!StdIn.isEmpty()) { int key = StdIn.readInt(); if(rank(key,a) != -1) StdOut.printf("%d is in whitelist\n",key); } } }

main:

public static void main(String[] args) { test("-","test.txt"); }