1800字普林斯顿大学课程浓缩笔记：程序员必知的算法之查找和排序算法(2)|C#教程

当前位置:

首页 > 编程开发 > c#教程 >

C#教程之1800字普林斯顿大学课程浓缩笔记：程序员必知的算法之查找和排序算法(2)

本站最新发布 C#从入门到精通
试听地址 https://www.xin3721.com/eschool/CSharpxin3721/

); 19 } 20 21 // power is present in n, so subtract power from n 22 else { 23 System.out.print(1); 24 n -= power; 25 } 26 27 // next smallest power of 2 28 power /= 2; 29 } 30 31 System.out.println(); 32 33 } 34 35}

3.4 二分查找求函数的近似解

假定函数f(x)是递增的，给定一个值y，我们的任务是发现一个值 x 使得 f(x) 近似等于 y, 我们开始于间隔 (lo,hi)，它一定包含x, 应用下面的迭代策略发现x:

step1: 计算 mid = lo + (hi-lo)/2
step2: 平凡情况，如果 hi-lo 小于阈值，则返回 mid 作为x的值
step3: 否则，测试 f(mid) > y 吗？如果是，则在区间(lo, mid)中查找，否则在区间(mid,hi)中查找。

这个过程的示意图如下，x搜索区间缩小到 (lo,mid).

3.5 二分查找应用广泛的前提条件

在一个数组中发现某个目标值，基于二分查找的前提是这个数组得是有序数组，只有这样，我们才能缩小搜索空间，找到目标值。下面这版代码是完整的二分查找代码，注意main函数中，首先对数组进行了sort排序，然后启用search函数。

 1import java.util.Arrays;
 2
 3public class BinarySearch {
 4
 5    // return the index of the key in the sorted array a[]; -1 if not found
 6    public static int search(String key, String[] a) {
 7        return search(key, a, 0, a.length);
 8    }
 9    public static int search(String key, String[] a, int lo, int hi) {
10System.out.println("lo  = " + lo);
11System.out.println("hi  = " + hi);
12        // possible key indices in [lo, hi)
13        if (hi <= lo) return -1;
14        int mid = lo + (hi - lo) / 2;
15        int cmp = a[mid].compareTo(key);
16        if      (cmp > 0) return search(key, a, lo, mid);
17        else if (cmp < 0) return search(key, a, mid+1, hi);
18        else              return mid;
19    }
20
21
22    // whitelist, exception filter
23    public static void main(String[] args) {
24        In in = new In(args[0]);
25        String s = in.readAll();
26        String[] words = s.split("\\s+");
27        System.err.println("Done reading words");
28
29        // sort the words (if needed)
30        Arrays.sort(words);
31        System.err.println("Done sorting words");
32
33        // prompt user to enter a word and check if it's there
34        while (!StdIn.isEmpty()) {
35            String key = StdIn.readString();
36            if (search(key, words) < 0) StdOut.println(key);
37        }
38    }
39}