Searching Algorithms: Sequential Search
. 前言
该博客用于本弱鸡复习巩固，打牢基础，还望各大佬不吝赐教。
. 基本思路
顺序查找是最简单最基本的查找方式
给定关键字 key 从数组中第一个元素开始，一直遍历到最后一个，直到找到该元素。改进顺序查找 与 顺序查找 改进顺序查找将数组成最后一位设置为标志位， 这样解决了每次将 角标 i 与 数组长度 n 作比较的麻烦，降低了算法复杂度。. 图片示例
. 算法复杂度分析
| 平均 | 最好 | 最坏 |
|---|---|---|
| O(n) | O(1) | O(1) |
| 平均查找次数为 (n+1)/2 | 第一次比较就找到 | 比较 n 次才找到,找不到则为 n+1 次 |
. 代码实现
1import java.util.ArrayList; 2import java.util.Collections; 3/** 4 * Sequential Search / Linear Search 顺序查找/线性查找 5 * 6 * 最简单最基本的查找方式 7 * 给定关键字 key 从数组中第一个元素开始，一直遍历到最后一个，直到找到该元素 8 * 9 * 改进顺序查找与顺序查找 10 * 改进顺序查找将数组成最后一位设置为标志位， 11 * 这样解决了每次将 角标i 与 数组长度n 作比较的麻烦，降低了算法复杂度。 12 * 13 * 算法复杂度分析 14 * 时间复杂度（平均） O(n) 平均查找次数为 (n+1)/2 15 * 时间复杂度（最坏） O(n) 比较 n 次才找到,找不到则为 n+1 次 16 * 时间复杂度（最好） O(1) 第一次比较就找到 17 */ 18public class SeqSearch { 19 20 public static void main(String[] args) { 21 22 //将 1-10 打乱排序 23 ArrayList a = new ArrayList (); 24 for (int i = 1; i < 10; i++) { 25 a.add(i); 26 Collections.shuffle(a); 27 } 28 System.out.println("Unordered Array :"); 29 System.out.println(a.toString()); 30 31 //定义查找关键字 32 int key = 4; 33 //顺序查找 34 seqSearch(key, a); 35 //改进顺序查找 36 advSeqSearch(key, a); 37 38 } 39 40 public static void seqSearch(int key, ArrayList a) { 41 //每次都要与10作比较 42 for (int i = 0; i < 10; i++) { 43 if (a.get(i) == key) { 44 System.out.println("Find key = " + key + " at index : " + i); 45 break; 46 } 47 } 48 } 49 50 public static void advSeqSearch(int key, ArrayList a) { 51 //将最后一位赋为key 52 a.add(key); 53 System.out.println("Unordered Array :"); 54 System.out.println(a.toString()); 55 int i = 0; 56 //从第0位开始，直到最后一位进行比较 57 //若最后 i=10 , 则证明被查找数组中找不到该元素key 58 while (!a.get(i++).equals(a.get(a.size() - 1))) { 59 } 60 61 System.out.println("If index = 10 , key does not exist ."); 62 System.out.println("Find key = " + key + " at index : " + (i - 1)); 63 } 64} 复制代码