74 searching 3 key Fig.3-1
75 2を探索 53を探索 3-1 5 2 1 4 3 7 4 を探索 Fig.3-1
76 3 linear searchsequential search 2 Fig.3-2 0 ❶ ❷ ❸ 配列の要素を先頭から順に走査していく 探索すべき値と等しい要素を発見 Fig.3-2 6 4 3 2
3-2Fig.3-3 77 5 Fig.3-3 0 ❶ ❷ ❸ ❹ ❺ ❻ 配列の要素を先頭から順に走査していく 配列の末端を通り越してしまった n n / 2 ㆒ n + 1 ㆓ n List 3-1
78List 3-1 // Chap03/SeqSearch.java import java.util.scanner; class SeqSearch { 3 //--- ankey ---// static int seqsearch(int[] a, int n, int key) { int i = 0; while (true) { if (i == n) return -1; if (a[i] == key) return i; i++; // -1 // public static void main(string[] args) { Scanner stdin = new Scanner(System.in); System.out.print(""); int num = stdin.nextint(); int[] x = new int[num]; // num for (int i = 0; i < num; i++) { System.out.print("x[" + i + "]"); x[i] = stdin.nextint(); 7 Ÿ x[0]22 Ÿ x[1]8 Ÿ x[2]55 Ÿ x[3]32 Ÿ x[4]120 Ÿ x[5]55 Ÿ x[6]70 Ÿ 120 Ÿ x[4] System.out.print(""); int ky = stdin.nextint(); // int idx = seqsearch(x, num, ky); // xky if (idx == -1) System.out.println(""); else System.out.println("x[" + idx + "]"); seqsearch a n key key key -1-1 i 0 while
3-2 79 while i == n a[i] == key while true List 3-2 for List 3-2 //--- ankey ---// static int seqsearch(int[] a, int n, int key) { for (int i = 0; i < n; i++) if (a[i] == key) return i; // return -1; // -1 Chap03/SeqSearchFor.java main List 3-1 main List 3-1 while break return for true while (true) { // for ( ; ; ) { // do { // while (true); while for do
80 3 ちり Fig.3-2 Fig.3-3 Fig.3-4 本来のデータ 番兵 ❸ 2 探索する値と等しい要素を発見 ❼ 5 探索する値と等しい要素を発見 ただし見つけたのは番兵 Fig.3-4 4 4 4 a[0] a[6] a[7] sentinel 2 a[7] 2 5 a[7] 5 4 4 4 a[7] List 3-1 List 3-3 1 7 8 seqsearchsen
3-2 key a[n] 81 List 3-3 // Chap03/SeqSearchSen.java import java.util.scanner; class SeqSearchSen { //--- ankey---// static int seqsearchsen(int[] a, int n, int key) { int i = 0; a[n] = key; while (true) { if (a[i] == key) break; i++; return i == n? -1 : i; // // public static void main(string[] args) { Scanner stdin = new Scanner(System.in); System.out.print(""); int num = stdin.nextint(); int[] x = new int[num + 1]; for (int i = 0; i < num; i++) { System.out.print("x[" + i + "]"); x[i] = stdin.nextint(); 7 Ÿ x[0]22 Ÿ x[1]8 Ÿ x[2]55 Ÿ x[3]32 Ÿ x[4]120 Ÿ x[5]55 Ÿ x[6]70 Ÿ 120 Ÿ x[4] // num + 1 System.out.print(""); int ky = stdin.nextint(); int idx = seqsearchsen(x, num, ky); // // xky if (idx == -1) System.out.println(""); else System.out.println("x[" + idx + "]"); List 3-1 while if if (i == n) // ㆒ if (a[i] == key) // ㆓ if 4 4 4 4 4 4 while 4 4 i n -1
82 3 binary search 39 a[5] 31 0 1 2 3 4 ❺ 6 7 8 9 10 39 a[6] a[10] a[8] 68 0 1 2 3 4 5 6 7 ❽ 9 10 a[6] a[7] 39 58 39 6 7 (6 + 7) / 2 6 0 1 2 3 4 5 ❻ 7 8 9 10 39 n a key pl pr pc pl 0pr n - 1pc (n - 1) / 2 Fig.3-5
3-3Fig.3-5 83 着目要素 ( 中央要素 ) pl pc pr ここには存在しない 探索範囲 pl 0 1 2 3 4 ❺ 6 7 8 9 10 0 1 2 3 4 5 6 7 ❽ 9 10 0 1 2 3 4 5 ❻ 7 8 9 10 pl pl pr pr pr 探索すべき値と等しい要素を発見 a[pc] key a[pc] < key a[pl] a[pc] key a[pc + 1] a[pr] pl pc + 1 a[pc] > key a[pc] a[pr] key a[pl] a[pc - 1] pr pc - 1 a[pc] key 6 Fig.3-6
84 pl 0 1 2 3 4 ❺ 6 7 8 9 10 pr 3 pl pr 0 1 ❷ 3 4 5 6 7 8 9 10 pl pr 0 1 2 3 4 5 6 7 8 9 10 pr pl pr 0 ❶ 2 3 4 5 6 7 8 9 10 pl 0 1 2 3 4 5 6 7 8 9 10 探索範囲がなくなった Fig.3-6 a[0] a[10] a[5] 31 key 6 a[5] a[0] a[4] a[2] 15 key 6 a[2] a[0] a[1] a[0] 5 key 6 pl pc + 1 1 pl pr 1 a[1] 7 key 6 pr pc - 1 0 pl pr List 3-4 n (n + 1) n - 1
3-385 List 3-4 // Chap03/BinSearch.java import java.util.scanner; class BinSearch { //--- ankey ---// static int binsearch(int[] a, int n, int key) { int pl = 0; // int pr = n - 1; // do { int pc = (pl + pr) / 2; // if (a[pc] == key) return pc; // else if (a[pc] < key) pl = pc + 1; // else pr = pc - 1; // while (pl <= pr); 7 Ÿ return -1; // x[0]15 Ÿ x[1]27 Ÿ public static void main(string[] args) { x[2]39 Ÿ Scanner stdin = new Scanner(System.in); x[3]77 Ÿ x[4]92 Ÿ System.out.print(""); x[5]108 Ÿ int num = stdin.nextint(); x[6]121 Ÿ int[] x = new int[num]; // num 39 Ÿ x[2] System.out.println(""); System.out.print("x[0]"); x[0] = stdin.nextint(); // for (int i = 1; i < num; i++) { do { System.out.print("x[" + i + "]"); x[i] = stdin.nextint(); while (x[i] < x[i - 1]); // System.out.print(""); int ky = stdin.nextint(); // int idx = binsearch(x, num, ky); // xky if (idx == -1) System.out.println(""); else System.out.println("x[" + idx + "]"); xx ceilingx 3.5 4
86 3 complexity time complexity space complexity //--- ---// static int seqsearch(int[] a, int n, int key) { int i = 0; while (i < n) { if (a[i] == key) return i; i++; return -1; // // Table 3-1 i 0
3-387 Table 3-1 List 3-3 seqsearchsen while for '*' 0 1 2 3 4 5 6 ---+------------------------------ * 0 * 1 * 2 a[2]
88 Table 3-2 3 int pl = 0; // //--- ---// static int binsearch(int[] a, int n, int key) { int pr = n - 1; // do { int pc = (pl + pr) / 2; // if (a[pc] == key) return pc; else if (a[pc] < key) pl = pc + 1; else pr = pc - 1; while (pl <= pr); // // // return -1; // Table 3-2 Fig.3-7
3-3 89 小 大 Fig.3-7 n a key idx static int searchidx(int[] a, int n, int key, int[] idx) "<-" "->" "+" 0 1 2 3 4 5 6 ---+------------------------------ <- + -> 3 1 2 3 5 6 8 9 <- + -> 1 1 2 3 5 6 8 9 a[1] 7 5 static int binsearchx(int[] a, int n, int key) 0 1 2 3 4 ❺ 6 7 8 9 10 1 3 5 7 7 7 7 8 8 9 9 0 1 2 ❸ 4 ❺ 6 7 8 9 10 1 3 5 7 7 7 7 8 8 9 9 配列の先頭を越えない範囲で 同じ値の要素が続く限り前方に走査