第 3 章 探索 Arrays.binarySearch
743 3-1 探索 探索 searching key 配列 探索 Fig.3-1 b c
75 a 6 4 3 2 1 9 8 2 b 64 23 53 65 75 21 3-1 53 c 5 2 1 4 3 7 4 Fig.3-1 a
763 3-2 線形探索 線形探索 linear search sequential search 2 Fig.3-2 2 a b c d Fig.3-2 a 6 b 4 c 3 d 2
77 5 Fig.3-3 aʰ 5 a 3-2 b c d e f ɡ ʰ Fig.3-3 n n / 2 n + 1 n List 3-1
783 List 3-1 Chap03/SeqSearch.java // import java.util.scanner; class SeqSearch { //--- ankey ---// static int seqsearch(int[] a, int n, int key) { int i = 0; while (true) { if (i == n) return -1; // -1 ㆒ if (a[i] == key) return i; // ㆓ i++; 実行例 7 Ÿ public static void main(string[] args) { x[0]22 Ÿ Scanner stdin = new Scanner(System.in); x[1]8 Ÿ x[2]55 Ÿ System.out.print(""); x[3]32 Ÿ int num = stdin.nextint(); x[4]120 Ÿ int[] x = new int[num]; // num x[5]55 Ÿ x[6]70 Ÿ for (int i = 0; i < num; i++) { 55 Ÿ System.out.print("x[" + i + "]"); x[2] x[i] = stdin.nextint(); 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 55 x[2] x[5] 2 i 0 while
79while ㆒ i == n ㆓ a[i] == key while true 2 3 while for List 3-2 3-2 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 p. Column 3-1 無限 実現 List 3-1 while break return for true while (true) { // for ( ; ; ) { // do { // while (true); while for 1 do
803 番兵法 sentinel methodfig.3-2 Fig.3-3 Fig.3-4 a 2 2 b 5 5 Fig.3-4 4 4 4 4 4 4 a[0] a[6] a[7] sentinel a2 a[7] 2 b5 a[7] 5 4 4 4 4 4 4 b a[7] List 3-1 List 3-3 1 7 8 seqsearchsen
81//--- 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); ㆒ ㆓ 叅 実行例 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] 3-2 List 3-3 // Chap03/SeqSearchSen.java import java.util.scanner; class SeqSearchSen { System.out.print(""); int num = stdin.nextint(); int[] x = new int[num + 1]; // num + 1 for (int i = 0; i < num; i++) { System.out.print("x[" + i + "]"); x[i] = stdin.nextint(); 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 + "]"); key a[n] 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
823 3-3 2 分探索 2 分探索 binary search 6 39 a[5]31 5 7 15 28 29 31 39 58 68 7 95 39 a[6] a[10] a[8] 68 5 7 15 28 29 31 39 58 68 7 95 a[6] a[7] 39 58 39 6 7 (6 + 7) / 2 6 5 7 15 28 29 31 39 58 68 7 95 39 n a key plprpc pl 0pr n - 1pc (n - 1) / 2 Fig.3-5 a
83a b pl pr 5 7 15 28 29 31 39 58 68 7 95 pl pr 5 7 15 28 29 31 39 58 68 7 95 3-3 pl pc pr c pl pr 5 7 15 28 29 31 39 58 68 7 95 Fig.3-5 39 ca[pc] key a[pc] < key a[pl] a[pc] key a[pc] a[pc + 1] a[pr] pl pc + 1 ab a[pc] > key a[pc] a[pr] key a[pc] a[pl] a[pc - 1] pr pc - 1 bc a[pc] key 6 Fig.3-6
843 a pl pr 5 7 15 28 29 31 39 58 68 7 95 b pl pr 5 7 15 28 29 31 39 58 68 7 95 c pl pr 5 7 15 28 29 31 39 58 68 7 95 d e pl pr 5 7 15 28 29 31 39 58 68 7 95 pr pl 5 7 15 28 29 31 39 58 68 7 95 Fig.3-66 a a[0] a[10] a[5] 31 key 6 a[5] a[0] a[4] b a[2] 15 key 6 a[2] a[0] a[1] c a[0] 5 key 6 pl pc + 1 1 pl pr 1 d a[1] 7 key 6 pr pc - 1 0 pl pr List 3-4 n (n + 1) n - 1
85//--- 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); return -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 System.out.println(""); 実行例 7 Ÿ x[0]15 Ÿ x[1]27 Ÿ x[2]39 Ÿ x[3]77 Ÿ x[4]92 Ÿ x[5]108 Ÿ x[6]121 Ÿ 39 Ÿ x[2] 3-3 List 3-4 // Chap03/BinSearch.java import java.util.scanner; class BinSearch { 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
863 計算量 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; // // List 3-1 seqsearch ㆒⓺ Table 3-1 i 0 ㆒ ㆕⓺ ㆓ 叅
87Table 3-1 ㆒ ㆓ 叅 ㆕ ⓹ ⓺ 3-3 max(a, b) a b 3-1 List 3-3p.81 seqsearchsen while for 3-2 '*' 0 1 2 3 4 5 6 ---+------------------------------ * 0 6 4 3 2 1 9 8 * 1 6 4 3 2 1 9 8 * 2 6 4 3 2 1 9 8 3x[2]
883 2 分探索 時間計算量 Table 3-2 //--- ---// 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); return -1; // Table 3-2 ㆒ ㆓ 叅 ㆕ ⓹ ⓺ 柒 ⓼ ⓽ ⓾ Fig.3-7
89Fig.3-7 3-3 n a key idx static int searchidx(int[] a, int n, int key, int[] idx) 8 a {1, 9, 2, 9, 4, 6, 7, 9 key 9 idx {1, 3, 7 3 3-3 3-4 "<-" "->" "+" 0 1 2 3 4 5 6 ---+------------------------------ <- + -> 3 1 2 3 5 6 8 9 <- + -> 1 1 2 3 5 6 8 9 2x[1] 3-5 7 5 a b a 1 3 5 7 7 7 7 8 8 9 9 b 1 2 4 6 7 8 9 1 3 5 7 7 7 7 8 8 9 9 static int binsearchx(int[] a, int n, int key)