首页 > Python基础教程 >
-
1800字普林斯顿大学课程浓缩笔记：程序员必知的算法之查找和排序算法(2)
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}
因此二分查找的使用前提是排序算法，下面这节详细介绍归并排序，最典型的排序算法之一。
4.1 排序算法
排序算法中归并排序算法应用很广泛，它是分治法的典型实例。关于 7 种常用的排序算法的纯碎源码，请参考文章：
纯碎coding：7个最常用的排序算法
4.2 归并排序
普林斯顿大学的算法课程要求每一个程序员都要清楚地掌握这个排序算法，可见其重要程度。
基本思想：如果数组长度为0或1，则它已经排序好了，否则把数组分为两半，独立的排序这两半，然后再融合它们。
4.3 归并排序例子
待排序的数组为： was had him and you his the but 应用归并排序的整个过程如下图所示：
框线图直观表示：
