６月２１日　オンライン分まとめ中
====== 探索(Searching) ======


=== 探索処理（サーチング、サーチ、search) ===


・有限のデータの中から、目的のデータを探す事
<code>
	例：配列を走査して、目的の値を見つける
	　 int iarray[10]={2, 5, 8, 1, 4, 7, 3, 6, 9, 0};
	                   0  1  2  3  4  5  6  7  8  9 ← index
           キー値６を探せ！　indexの０からたどっていき、index7でキー値6を見つけたよ。
　　　　　　探索結果　＝＞　iarray[7]が６に一致
</code>

  * 著名な探索アルゴリズム
    * 線形探索
    * 二分探索
    * ハッシュ法

<WRAP center round box 80%>
性能（場合による）＝　探索の速さ　＝　処理の少なさ <= 繰り返し数と比較数\\
ハッシュ法 ＞　二分探索　＞　線形探索\\
</WRAP>

データ形式：\\
配列：\\
<code>
配列＝＞同じ型のデータが複数あり、名前とインデックスで表現されたもの
(double a[5]; => a[0] ～a[4]がdouble型で用意される）
</code>
レコード：\\
<code>
　　 （キー項目）|  （キーに付属した情報)
	商品番号 |     商品名      | 単価
	  A001   |  ハンバーガー   | 200 
	  A003   | チーズバーガー　| 260    <=　レコード形式（固定幅データ）
	　A005   | エッグサンド    | 240
          A007   | アイスコーヒー　| 120
          …　　 |    　…　	   |  …
</code>
表＝テーブル(table)\\



==== 「線形探索法」(逐次探索法：Linear Search Algorithm) ====

・データ列（レコード、配列など）を先頭から順番に一個ずつ逐次、キー値（探索値）と比較して、
　見つかるまで走査する方法


**　例題６－１ **
<code>
　　　レコード
      index| CarNo |  CarName　　
        0  | 1003  | "MarkⅡ"
        1  | 1012  | "Chaser"
        2  | 1053  | "Mr2"
        3  | 1031  | "Rx-7"
        4  | 1021  | "Minica"
        5  | 1075  | "Legacy"

　・CarNoで探して、車種名を出力する探索
	変数として必要なもの　→　indexをたどるためのカウンタ変数 i 
　　　　　　　　　　　　　　　　　探すCarNoを保存しておく変数（キー値＝探索キー）var=1053
	例）探索キーが１０５３で入力されたとき（P９２）　結果"Mr2"と表示される
	    
	    if(var == 1053 && i<=最大データ数)
	    {
               carNameを出力
   	    }
</code>

・番兵法
<code>
	    if(var == 1024 && i<=最大データ数（Ｎ）)　//アルゴリズムとしては、比較回数は２
	    {
               carNameを出力
   	    }
   ・データが見つからなかったときは最大データ数Ｎｘ２回の比較が必要
　 ・最大データ数を１増やしておいて、最後に番兵を配置することで、比較回数を減らす作戦（ストラテジー）

　　  index| CarNo |  CarName　　
        0  | 1003  | "MarkⅡ"
        1  | 1012  | "Chaser"
        2  | 1053  | "Mr2"
        3  | 1024  | "Rx-7"
        4  | 1021  | "Minica"
        5  | 1075  | "Legacy"   
　　　  … |  … 　|   …   
        N  |  XXX  | "XXXXX"
       N+1 | 1024  | -------    
             ＝探索キー＝番兵

	while(var != 1024)　//アルゴリズムとしては、比較回数は１
	{
           carNameを出力
	   i = i + 1;
   	}
	
	if(i==N+1){
	   データが見つからなかったときの処理;
	}else{
	   データが見つかった時の処理
	}
	//(N+1) x 1 Nは０以上
</code>

ーーーーーーーーーーー【複合条件】ーーーーーーーーーーーーーーーーーーーーーーーーーー\\
<code>
・比較の時に複数の条件を組み合わせて真偽値を決める
i>0
i<=10
・ＡＮＤ →　且つ　　両方同時に成り立てば真　 C/C++では　&& (shift+6)
　　　　　　 例：ｘが０以上６未満（数学だと０≦ｘ＜６）
	　　　　 ｘが０以上　且つ　６未満　 x >= 0  &&  x < 6					

・ＯＲ　 →　又は　　どちらかが成り立てば真　 C/C++では　|| (shift+\(バックスペースの左）)
             例：xが０以下　または、ｘが６より大きい（数学だと x ≦ 0, x ＞ 6）
　						       x <= 0 || x > 6

・Ｎｏｔ　→　～でない　条件を否定して真偽を逆転させる
	     not(x>=0) ＝＞ x < 0と同値　　C/C++では　!(x >= 0) と書く
　　　　　　  !(x >= 0) == (x < 0)

剰余の演算子 % → x%3 xを３で割ったあまりが結果
割り切れる＝余りが０

変数int ｘにおいて、
・３で割り切れて、かつ５で割り切れる　x%3==0 && x%5==0  
・３で割り切れる、正ではない整数      !(x>=0) && x%3==0
				          x<0 && x%3==0
・３でも、５でも割り切れない	      !(x%3==0) && !(x%5==0)

このような複合条件が１度に書けるようになる。
ーーーーーーーーーーー【複合条件】ーーーーーーーーーーーーーーーーーーーーーーーーーーー

順次
選択（条件分岐）
繰り返し（継続条件、終了条件）　2%3==0 -> 2%3=2 -> 2==0? -> false 条件＝真偽値です。
</code>


=== 二分探索（バイナリーサーチ Binary Search)  ===
<code>
・相手にしているデータ→整列済みデータ(昇順化、降順に並んだデータ）
サンプルデータ[3, 5, 6, 8, 12, 34, 36, 37, 45, 49] 
　　　　　　　 0  1  2  3   4   5   6   7   8   9
例）
・探索キー＝３７
サンプルデータ[3, 5, 6, 8, 12, 34, 36, 37, 45, 49] 
　　　　　　　 0  1  2  3   4   5   6   7   8   9
サンプルデータ[                34, 36, 37, 45, 49] 
　　　　　　　                  5   6   7   8   9
サンプルデータ[                34, 36, 37, 45, 49] 
　　　　　　　                  5   6   7   8   9
サンプルデータ[                34, 36, 37        ] 
　　　　　　　                  5   6   7  
サンプルデータ[                34, 36, 37　      ] 
　　　　　　　                  5   6   7  
サンプルデータ[               　　　　 37　      ]  37発見
　　　　　　　                  　　　　7
</code>