position_search (binary search)
挿入位置の探索

ミニレポート第 3 回課題

第2回課題で作成した プログラムに以下に述べる関数 position_search を追加する． （report02.c を report03.c という名前でコピーし， report03.c のほうに書き加える）

関数 position_search は，データを挿入するときに配列 table 中の挿入するべき場所の添字を返すを関数である． 仕様は以下の通りとする．

position_searchの仕様

• 前提：教科書List2.1の table 配列に要素がメンバ key の値が昇順に なるようにあらかじめ整列された状態で格納されており， 要素の個数はグローバル変数 n に格納されている． （例は授業ページ図1.3）
• 引数：整数とする．
• 返り値：table にキーの値が入力値であるような要素を追加 する場合の適当な位置の添え字を返す．入力値と等しい値をキーとする 要素がすでにあった場合はその最後に挿入するとしてその位置の 添え字を返す．関数の書き出しは
  int position_search(int key)
  でよい． 例えば配列 table が以下の内容であるとき，

  	keyの値	dataの値
  table[0]	1	200
  table[1]	3	350
  table[2]	4	520
  table[3]	8	150
  table[4]	14	920
  table[5]	14	360
  table[6]	18	250
  table[7]	20	260
  table[8]	21	950
  table[9]	25	260

  position_search に与えられた引数が 2 であれば key が 1, data が 200 である最初のデータの後（今は table[1] のデータが入っている場所） に挿入するのが正しいので position_search は添字 1 を返す． 引数が 4であれば添字 3 を返し， 引数が14であれば添字 6 を返す． 引数が26であれば添字 10 を返す．
• position_search 内ではキーボードからの入力や 画面への出力を行なってはならない．

ヒント1： 教科書 List 2.1 の search は整数を引数とする関数で， 配列 table の要素の中にメンバ key の値が引数で指定した ものがあれば，そのメンバ data の値を返し， 無ければ -1 を返す関数である．これを参考に position_search を 作ることができる．余裕のある学生は教科書 List 2.2 の binary_search を ベースに作るほうが難易度は高いが高速なのでチャレンジして欲しい．

ヒント2： いきなり完成品を作ろうとせずに以下の順で作ってテストしてみるとよい．

1. まずは関数の入力値 key が table 内に存在するキー （1,3,4,8,14,18,20,21,25）だったときだけ 正しく動くものでいいので， そのキーがある番号（配列tableの添字，0から9）を返す 関数を作る．
2. まず，key の値が table 内の table[i].key の最大値 より小さい場合（上の例ではkeyが24以下のとき）だけを 考えて，そういうときに正しく課題 3 の答えを 計算するプログラムを作る． 上の段階のプログラムは i を 0 から増やしてゆき， table[i].key が key と等しくなるまで i を増やす， という形になるはずである．これを変更して table[i].key が key の値を初めて超えたとき， その i を返すようにする．この i の値が この課題で求める挿入すべき場所の添字 i の値になる．
3. 残りは key の値が table 内の table[i].key の最大値 以上の場合にも正しく動くように調整することである． この場合は table[i].key が key の値を超えないので 上記プログラムだけでは対応できない．その対応を考える．

プログラム全体についての注意

• プログラムファイルの設置場所は演習サーバ sirius.yamamotolab.jt.u-tokai.ac.jp 上の自分のホームディレクトリ 直下の c ディレクトリとし， ファイル名は report03.c とする
• プログラム全体としては第2回課題 で作成したものをベースにして それに posision_search を追加したものを作成せよ． 以前に作成した関数には手を加えず，(binary_search 関数や table 構造体の中を変更してはいけない．print_all もデバッグに 便利なので残すこと） 教科書List2.2 に書かれている部分とmain 関数との間に 関数 position_search（や必要であれば自作関数）を挿入せよ．
• main 関数を適当に何度か書き換えて動作させ， position_search が正しく動作していることを確認せよ． レポート提出時には main 関数だけをこちらで用意したもので 置き換えてテストを行うので提出時の report03.c の main 関数内はどんなものでもよい．

注意事項

• 締切は 2023年10月29日 とする．
• メールでプログラムを提出する必要はない
• 締切後はレポート受理，非受理の結果がわかるまで上書き しないように注意せよ

受理した学生のリストを 1 クラス提出者 2 クラス提出者 3 クラス提出者 に掲載する． 締切までに提出したにもかかわらず締切後一週間を過ぎても掲載されていない 場合は山本 <hiroshi@tokai.ac.jp>まで連絡せよ． 未提出の学生はすみやかに再提出せよ． 再提出後一週間経っても掲載されない場合も 山本まで連絡せよ．