习题1.1.38
二分查找与暴力查找。根据1.1.10.4节给出的暴力查找法编写一个程序 BruteForceSearch，在你的计算机上比较它和 BinarySearch处理largeW.txt 和 largeT.txt所需的时间。
要点分析
一. 暴力查找法
1.1.10.4节（课本第29页底部）
public static int rank(int key, int[] a) {
for (int i = 0; i < a.length; i++)
if (a[i] == key) return i;
return -1;
}
二. BinarySearch
关于BinarySearch类实现在课本第5页中部，如果您没带课本
在《算法第四版》课后练习题1.1.21-1.1.25答案 一文中的第1.1.22题中给出了BinarySearch类的具体代码和使用范例。
其实有关二分查找，我们在后面的学习中会专门学习，所以这里只简单提一下，首先，二分查找的速度非常之快，但是也有缺点，就是该算法满足以下两个条件：
- 必须采用顺序存储结构
- 必须按关键字大小有序排列[1]
所以我们在使用的过程中，可以用Arrays.sort();方法先将数组排序
三. 基于文件的输入输出
因为要用到两个文件中数据来测试两个方法的执行效率，所以我们会用到基于文件的输入输出这个知识点，在课本的第25页有详细的讲解，下文的知识要点中，我们也会讲解如何基于文件输入输出。
四. 数据下载
laegeW.txt 和 largeT.txt
c8mc
五. In类使用
我们如何在程序中调用上文中的laegeW.txt 和 largeT.txt 这两个文件的中的数据呢，在课本的第5页，BinarySearch中曾经给出过使用方法，采用的是课本标准库中的In和Out两个类（课本第25页），这里再以一个具体实例，解释一下如何使用该类：
首先，我们在E盘Test文件夹中创建一个test.txt的文件，并编辑1 2 3 4 5 6 7 8 这几个数字保存（中间用空格或者回车隔开）
import edu.princeton.cs.algs4.In;
public class Test3 {
public static void main(String[] args) {
int[] a = In.readInts(args[0]);
//注意这里的In是采用基于文件的输入，详情可以查看《算法》第25页
//args[0]通过命令行传入一个txt文本路径，比如E:\Test\test.txt
//这里Test.txt里的内容为1 2 3 4 5 6 7 8 9，此时已经存入a这个数组中
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
}
}
输出：
1 2 3 4 5 6 7 8 9
六. 统计时间
如何查看系统处理这个两个文件需要的时间呢？我们一般采用下面的方法进行检验：
public static void main(String[] args) {
long startTime = System.currentTimeMillis();//获取当前的时间
long sum = 0;
for (int i = 1; i <= 10000000; i++) {
sum += i;
}
System.out.println(sum);
long endTime = System.currentTimeMillis();
System.out.println("该程序一共运行了："+(endTime-startTime)+"ms");
}
输出：
50000005000000
该程序一共运行了：7ms
参考答案
首先我们来看在largeW.txt文件中，100万个数据，BruteForceSearch的运行时间为5ms
import edu.princeton.cs.algs4.In;
import java.util.Arrays;
public class Thirty_eight {
/**
* @description: 暴力查找法
* @param: key 要查找的元素
* @param: a 在a这个数组中查找
* @return: 查找的元素所以
*/
public static int rank(int key, int[] a) {
for (int i = 0; i < a.length; i++)
if (a[i] == key) return i;
return -1;
}
public static void main(String[] args) {
int[] a = In.readInts(args[0]);
long time1 = System.currentTimeMillis();//获取当前的时间
int b = rank(122922297, a);
//为了突出比较结果，我在两个文档的最后面添加了一个数据中最大的数字122922297
// 作为要查找的元素，索引为100,0000
if (b != -1)
System.out.println("您查找的元素索引为" + b);
else
System.out.println("您查找的元素不存在");
long time2 = System.currentTimeMillis();
System.out.println("该程序一共运行了：" + (time2 - time1) + "ms");
}
}
输出：
您查找的元素索引为1000000
该程序一共运行了：5ms
而BinarySearch方法为0ms：
import edu.princeton.cs.algs4.In;
import java.util.Arrays;
public class Thirty_eight {
/**
* @description: 二分查找（BinarySearch)方法，课本第5页
* @param: a 要查找的数组
* @param: key 要查找的元素
* @return: 要查找的元素的索引
*/
public static int rank(int[] a, int key) {
int lo = 0;
int hi = a.length - 1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (key < a[mid]) {
hi = mid - 1;
} else if (key > a[mid]) {
lo = mid + 1;
} else {
return mid;
}
}
return -1;
}
public static void main(String[] args) {
int[] a = In.readInts(args[0]);
Arrays.sort(a);
long time1 = System.currentTimeMillis();//获取当前的时间
int b = rank(a,122922297);
//为了突出比较结果，我在两个文档的最后面添加了一个数据中最大的数字122922297
// 作为要查找的元素，索引为100,0000
if (b != -1)
System.out.println("您查找的元素索引为" + b);
else
System.out.println("您查找的元素不存在");
long time2 = System.currentTimeMillis();
System.out.println("该程序一共运行了：" + (time2 - time1) + "ms");
}
}
您查找的元素索引为1000000
该程序一共运行了：0ms
接下来是 largeT.txt 文件中，1000万个数据，BruteForceSearch的运行时间为8ms
import edu.princeton.cs.algs4.In;
import java.util.Arrays;
public class Thirty_eight {
/**
* @description: 暴力查找法
* @param: key 要查找的元素
* @param: a 在a这个数组中查找
* @return: 查找的元素所以
*/
public static int rank(int key, int[] a) {
for (int i = 0; i < a.length; i++)
if (a[i] == key) return i;
return -1;
}
public static void main(String[] args) {
int[] a = In.readInts(args[0]);
long time1 = System.currentTimeMillis();//获取当前的时间
int b = rank(122922297, a);
//为了突出比较结果，我在两个文档的最后面添加了一个数据中最大的数字122922297
// 作为要查找的元素，索引为1000,0000
if (b != -1)
System.out.println("您查找的元素索引为" + b);
else
System.out.println("您查找的元素不存在");
long time2 = System.currentTimeMillis();
System.out.println("该程序一共运行了：" + (time2 - time1) + "ms");
}
}
输出：
您查找的元素索引为10000000
该程序一共运行了：7ms
再来看看BinarySearch方法依旧是0ms：
import edu.princeton.cs.algs4.In;
import java.util.Arrays;
public class Thirty_eight {
/**
* @description: 二分查找（BinarySearch)方法，课本第5页
* @param: a 要查找的数组
* @param: key 要查找的元素
* @return: 要查找的元素的索引
*/
public static int rank(int[] a, int key) {
int lo = 0;
int hi = a.length - 1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (key < a[mid]) {
hi = mid - 1;
} else if (key > a[mid]) {
lo = mid + 1;
} else {
return mid;
}
}
return -1;
}
public static void main(String[] args) {
int[] a = In.readInts(args[0]);
Arrays.sort(a);
long time1 = System.currentTimeMillis();//获取当前的时间
int b = rank(a,122922297);
//为了突出比较结果，我在两个文档的最后面添加了一个数据中最大的数字122922297
// 作为要查找的元素，索引为1000,0000
if (b != -1)
System.out.println("您查找的元素索引为" + b);
else
System.out.println("您查找的元素不存在");
long time2 = System.currentTimeMillis();
System.out.println("该程序一共运行了：" + (time2 - time1) + "ms");
}
}
您查找的元素索引为10000000
该程序一共运行了：0ms
可以看到，BinarySearch方法再数据量越大的文件中，优势突出越明显。
（注意：电脑配置不同，这里程序的运行结果是不一样的。）
参考资料
[1] 百度百科：二分查找
请登录之后再进行评论