文章目录

• 0.前言
• 1.功能
• 2.示例
• • 有两个名单tinyW.txt和tinyT.txt，将tinyT.txt名单中不在tinyW.txt的数据打印出来
  • • ① 实现原理
    • ② 实现代码
    • ③ 性能分析

0.前言

• 最近才开始学算法，学习的材料是《算法 第四版》java语言描述，我会在接下来的学习中运用以下步骤学习记录，望广大读者朋友能够喜欢，也请多多提提意见。
• 首先我会说明这个算法提供了什么功能，拿来干嘛的，然后我会列几个例子来加深对这种算法的理解和应用，每个例子我都会进行实现原理的描述，有图有真相，还有它的代码，代码也会有注释分析，最后性能分析
• 最近才刚学，所以后期我还会写性能分析，实际应用等，将书中的精华都总结下来，同时后期我也会刷题leetcode，将刷到的题目分类，会重新加入到各篇文章的例子中,初步估计会是以链接的方式载入。

1.功能

• 其实功能不必说什么，名字已经能说明一切，就是查找功能，从海量的数据中查找你想要的数据。

2.示例

有两个名单tinyW.txt和tinyT.txt，将tinyT.txt名单中不在tinyW.txt的数据打印出来

① 实现原理

• 算法是由静态方法rank()实现的，它接受一个整数键key和一个已经有序的int数组作为参数。 如果该键存在于数组中则返回它的索引，否则返回-1。
• 算法使用两个变量1o和hi,并保证如果键在数组中则它一定在a[lo…hi]中，然后方法进入一个循环，不断将数组的中间键(索引为mid)和被查找的键比较。
• 如果被查找的键等于a[mid]，返回mid;否则算法就将查找范围缩小一半，如果被查找的键小于a[mid]就继续在左半边查找，如果被查找的键大于a[mid]就继续在右半边查找。算法找到被查找的键或是查找范围为空时该过程结束。
• 实现图解：

② 实现代码

package Chapter1.Section11.cs1110;import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;import java.util.Arrays;public class BinarySearch {/*** This class should not be instantiated.*/private BinarySearch() {}// 查询key是否在数组a中，在就返回mid索引，不在就返回-1.public static int indexOf(int[] a, int key) {int lo = 0;int hi = a.length - 1;while (lo <= hi) {int mid = lo + (hi - lo) / 2;if (key < a[mid]) hi = mid - 1;else if (key > a[mid]) lo = mid + 1;else return mid;}return -1;}//个人感觉没有必要，这里只是传递了一下，不知道作者是怎么想的public static int rank(int key, int[] a) {return indexOf(a, key);}public static void main(String[] args) {// 从文件中读取数据In in = new In(args[0]);//这里有几个打印语句，我就是好奇想知道它存的是啥System.out.println("in：" + in.toString());System.out.println("in对象的内容：" + Arrays.toString(args));int[] whitelist = in.readAllInts();System.out.println("whitelist：" + whitelist.toString());System.out.println("whitelist数组未排序：" + Arrays.toString(whitelist));//排序数组Arrays.sort(whitelist);System.out.println("whitelist数组已排序：" + Arrays.toString(whitelist));// read integer key from standard input; print if not in whitelistwhile (!StdIn.isEmpty()) {int key = StdIn.readInt();//这里只是想看一下key是什么。标准输入的数据是啥System.out.print(key + ",");if (rank(key, whitelist) == -1)//这里我改了一下，*x*即为tinyT.txt中不再tinyW.txt中的数据StdOut.print("*" + key + "*,");}}
}

③ 性能分析

• 二分查找快是因为它只需检查很少几个条目(相对于数组的大小)就能够找到目标元素( 或者确认目标元素不存在)。
• 这里先简单描述一下，性能分析还没学，后期补充进来

参考：《java算法第四版》

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！