２分探索アルゴリズムでは、探索すべきキー値と同じ値をもつ要素が複数存在する場合、それらの要素の先頭要素を見つけるとは限らない。たとえば、以下に示す配列から7を探索すると、中央要素のインデックスである5を見つけることになる。 ２分探索アルゴリズムによって探索に成功した場合、その位置から先頭側へ走査することによって、複数の要素が一致する場合でも、最も先頭側に位置する要素のインデックスを見つけられる。  そのように改良したメソッドを作成せよ。 static int binSearchX (int[] a , int n , int key ) |
// 演習3-5 // ２分探索（一致する先頭要素を見つける） import java.util.Scanner; class BinSearchX { //--- 配列aの先頭n個の要素からkeyと一致する要素を２分探索 ---// static int binSearchX(int[] a, int n, int key) { int pl = 0; // 探索範囲先頭のインデックス int pr = n - 1; // 〃 末尾のインデックス do { int pc = (pl + pr) / 2; // 中央要素のインデックス if (a[pc] == key) { for ( ; pc > pl; pc--) // keyと等しい先頭の要素を探す if (a[pc - 1] < key) break; 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("昇順に入力してください。"); 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 = binSearchX(x, num, ky); // 配列xから値がkyの要素を探索 if (idx == -1) System.out.println("その値の要素は存在しません。"); else System.out.println("その値は" + "x[" + idx + "]にあります。"); } }
// 演習4-2 // int型両頭スタックの利用例（IntStackX2クラスの全メソッドを利用） import java.util.Scanner; class IntStackX2TesterEx { public static void main(String[] args) { Scanner stdIn = new Scanner(System.in); IntStackX2 s = new IntStackX2(10); // 最大10個プッシュできる両頭スタック while (true) { int menu, n, x = 0; System.out.println("現在のデータ数："+ "Ａ：" + s.size(IntStackX2.AorB.StackA) + "Ｂ：" + s.size(IntStackX2.AorB.StackB)); System.out.print("(1)Ａにプッシュ (2)Ａからポップ (3)Ａからピーク " + "(4)Ａをダンプ (5)Ａから探索 (6)Ａを空にする\n" + "(7)Ｂにプッシュ (8)Ｂからポップ (9)Ｂからピーク " + "(10)Ｂをダンプ (11)Ｂから探索 (12)Ｂを空にする\n" + "(13)情報表示 (0)終了："); if ((menu = stdIn.nextInt()) == 0) break; switch (menu) { case 1: // Ａにプッシュ System.out.print("データ："); x = stdIn.nextInt(); try { s.push(IntStackX2.AorB.StackA, x); } catch (IntStackX2.OverflowIntStackX2Exception e) { System.out.println("スタックが満杯です。"); } break; case 2: // Ａからポップ try { x = s.pop(IntStackX2.AorB.StackA); System.out.println("ポップしたデータは" + x + "です。"); } catch (IntStackX2.EmptyIntStackX2Exception e) { System.out.println("スタックが空です。"); } break; case 3: // Ａからピーク try { x = s.peek(IntStackX2.AorB.StackA); System.out.println("ピークしたデータは" + x + "です。"); } catch (IntStackX2.EmptyIntStackX2Exception e) { System.out.println("スタックが空です。"); } break; case 4: // Ａをダンプ s.dump(IntStackX2.AorB.StackA); break; case 5: // Ａから探索 System.out.print("探索するデータ："); x = stdIn.nextInt(); n = s.indexOf(IntStackX2.AorB.StackA, x); if (n >= 0) System.out.println("頂上から" + (s.size(IntStackX2.AorB.StackA) - n) +"番目に存在します。"); else System.out.println("そのデータはありません。"); break; case 6: // 空にする s.clear(IntStackX2.AorB.StackA); break; case 7: // Ｂにプッシュ System.out.print("データ："); x = stdIn.nextInt(); try { s.push(IntStackX2.AorB.StackB, x); } catch (IntStackX2.OverflowIntStackX2Exception e) { System.out.println("スタックが満杯です。"); } break; case 8: // Ｂからポップ try { x = s.pop(IntStackX2.AorB.StackB); System.out.println("ポップしたデータは" + x + "です。"); } catch (IntStackX2.EmptyIntStackX2Exception e) { System.out.println("スタックが空です。"); } break; case 9: // Ｂからピーク try { x = s.peek(IntStackX2.AorB.StackB); System.out.println("ピークしたデータは" + x + "です。"); } catch (IntStackX2.EmptyIntStackX2Exception e) { System.out.println("スタックが空です。"); } break; case 10: // Ｂをダンプ s.dump(IntStackX2.AorB.StackB); break; case 11: // Ｂから探索 System.out.print("探索するデータ："); x = stdIn.nextInt(); n = s.indexOf(IntStackX2.AorB.StackB, x); if (n >= 0) System.out.println("頂上から" + (s.size(IntStackX2.AorB.StackB) - (s.capacity() - n) + 1) +"番目に存在します。"); else System.out.println("そのデータはありません。"); break; case 12: // 空にする s.clear(IntStackX2.AorB.StackB); break; case 13: // 情報表示 System.out.println("容量：" + s.capacity()); System.out.println("Ａのデータ数：" + s.size(IntStackX2.AorB.StackA)); System.out.println("Ｂのデータ数：" + s.size(IntStackX2.AorB.StackB)); System.out.println("Ａは空" + (s.isEmpty(IntStackX2.AorB.StackA) ? "です。" : "ではありません。")); System.out.println("Ｂは空" + (s.isEmpty(IntStackX2.AorB.StackB) ? "です。" : "ではありません。")); System.out.println("満杯" + (s.isFull() ? "です。" : "ではありません。")); break; } } } }
