出席の確認はOpenLMS の 3 限のコマを用いて行う． 3限の授業時間中に出席登録を完了せよ．
この授業のトップページから レポートのページに移動し， レポートの提出状況を常に確認せよ．
二分探索のポイントは，一回のチェックごとに 探索範囲が半分に減ることである．探索対象の リストの要素数が n ならばlog n 回のチェック で探索範囲が 1 個になるのでチェックが終了する． これにより O(log n) の計算量となる．
探索の進行に従って現在「可能性が残っている範囲」 の変化を正確に把握してえおく必要がある． これは変数 high と low によって行われる． table[low] から table[high] までの間が 可能性の残っている範囲である状態をキープする． 最初は low = 0, high = n-1 として，要素全体 を探索対象とした状態からスタートする．
middle は low と high の中間の要素になるように middle = (low + high) / 2 で計算される． C では（整数）/（整数）の式は， 結果が整数になるように切り捨てが行われることに注意せよ． この計算により，table[low] から table[high] の要素数が 奇数の場合は table[middle] はちょうど中間の要素となり， 要素数が偶数の場合は中間点は要素と要素の間になるので その前のほうの要素が table[middle] となるように middle の値が設定される．
二分探索は線形探索に比べて圧倒的に高速に検索できるが， データをあらかじめ整列した状態で保存しなければならない という制約がある．これはデータを追加するときに問題となる．
線形探索ではデータはどんな順序で保存していて探索の計算量は 変わらないのでデータを追加するときは，単純に最後尾に 追加すればよい．(List 2.3) オーダーO(1) つまり，定数時間でできる．
二分探索ではデータはしかるべき位置に保存しなければならない． データを挿入すべき位置は二分探索で求めることが できるのだが（O(log n)），そこから後ろのデータ全て（平均n/2個） を一個づつ後ろにずらさなくてはならない．(List 2.4) 結果，データの追加には O(n) の時間がかかってしまう．
P.19 List 2.4 の (4) の文は table[pos].data = data; の間違い．また，最後に (5) として n++; を追加する．
データの登録は線形探索が速く，探索は二分探索が速い． このことから，実際に使われる場面を考えて， 登録操作が多い場面に使われるのか，探索操作が多い場面に 使われるのかでどちらのアルゴリズムを採用するか選ぶ必要がある．
どちらかというと理論というより現場で速く動作することを重視した方法．
ハッシュ法の計算量の厳密な解析は難しいが，用意する配列の サイズが十分大きければ登録，検索ともO(1)とみなせる．
大きなメモリを用意しないと高速に動作しないという欠点がある．
オーダー表記では比例定数は無視される．たとえば 10n の時間がかかるアルゴリズムと n2 の時間のものとがあった場合，小さい n の入力については 比例定数の効果が強く，n2 のアルゴリズムのほうが速い，という場合も多い．
オーダー表記で優れたプログラムは高いコーディング技術を 要するものが多く，先述の比例定数が大きいものが多い． また，正しくコーディングするのに必要なコストが大きいことも無視できない． あまり繰り返し使わないプログラムならオーダー表記の 性能よりも速く間違いのないコーディングができることの ほうが重視されることも多い．
データ型とその型に対する一連の操作を組にしたもの
例えば「学生証番号」，「氏名」，「成績」，を 一人分の学生データとすると，多数の学生データ要素の集合に 対して，「一人分の要素を追加する」， 「指定された学生証番号の学生データを表示する」， 「指定された学生証番号の学生データを変更する」， 「指定された学生証番号の学生データを削除する」， 「成績順に全データを整列する」，などの操作が考えられる． これらを組にしたものがが抽象データ型．
抽象データ型に含まれるデータをプログラミング言語の提供する データ構造の機能を使って具体的に実装する． 例えば上の例で挙げたデータを以下のような構造体と
struct student {
char number[20];
char name[20];
int score;
} table[100];
図2.1 データ構造の例
この構造体の配列に対して抽象データ型で述べた 挿入，表示，変更，削除，整列などを行う関数とを セットにして作成する．
第 2 回課題「要素の出力」 を提出せよ．