Chinaunix首页 | 论坛 | 博客
  • 博客访问: 209277
  • 博文数量: 136
  • 博客积分: 2919
  • 博客等级: 少校
  • 技术积分: 1299
  • 用 户 组: 普通用户
  • 注册时间: 2011-03-11 09:08
文章分类

全部博文(136)

文章存档

2013年(1)

2011年(135)

我的朋友

分类: Java

2011-08-31 11:36:37

  1. public class Searching {
  2.     
  3.     /* Binary Search */
  4.     
  5.     public static int search(String key, String[] a) {
  6.         return search(key, a, 0, a.length);
  7.     }
  8.     
  9.     /** binary search implement
  10.       * key string sourght
  11.       * a[] sorted list of strings
  12.       * lo smallest possible index
  13.       * hi-1 largest possible index
  14.       * */
  15.     public static int search(String key, String[] a, int lo, int hi) {
  16.         
  17.         if (hi <= lo) return -1;
  18.         int mid = lo + (hi-lo)/2;
  19.         int cmp = a[mid].compareTo(key);
  20.         if (cmp > 0) return search(key, a, lo, mid);
  21.         else if (cmp < 0) return search(key, a, mid+1, hi);
  22.         else return mid;
  23.     }
  24.     
  25.     /* Sequence searching algorithm */
  26.     public static int searchSequence(String key, String[] a) {
  27.         int N = a.length;
  28.         for (int i = 0; i < N; i++)
  29.             if (a[i].compareTo(key) == 0)
  30.             return i;
  31.         return -1;
  32.     }
  33.     
  34.     /* Exception filter. Read a sorted list of strings from a whitelist file,
  35.      * then print out all strings from standard input not in the whitelist.
  36.      */
  37.     public static void main(String[] args) {
  38.         In in = new In(args[0]);
  39.         String s = in.readAll();
  40.         String[] words = s.split("\\s+"); // Separated by "whitesapce"
  41.         while (!StdIn.isEmpty()) {
  42.             String key = StdIn.readString();
  43.             if (search(key, words) == -1)
  44.                 System.out.println(key);
  45.         }
  46.     }
  47. }
阅读(335) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~