配列の探索


<教科書第3章範囲>

線形探索(逐次探索)
一般的に、配列に対しては線形探索が行われます。先頭から値を比較していき、目的の値と一致するものがあるかないかをひたすら調べることになります。
int test[10]={3,23,5,8,32,6,50,7,4,13}; int target = 50; for(int i=0;i<10;++i){ if(target==test[i]){ printf("見つかりました\n"); return 0; } } printf("見つかりませんでした\n"); return 0;

番兵法(線形探索の改善)
配列の末尾に検索対象となる値を入れておくことで、末端チェックを省略できる。

int banhei(){

 int
test[11]={3,23,5,8,32,6,50,7,4,13};
 int target = 50;

 test[10]=target; //末尾に検索対象を入れる
  while(1){
   if(target==test[i]){
    printf("見つかりました\n");
    break;
   }
   i++
  }
 return i==target?-1:i;
}




2分探索
データがソートされていれば、2分探索が有効である。


//前もってソートしておく
int test[10]={1,2,3,4,5,6,7,8,9,10}; //探索範囲左端 int left=0; //探索範囲右端 int right=9; //中央の位置 int mid; //検索値     int target =3   //範囲がなくなるまで while(min<=max){ mid=(min+max)/2; //一致するか if(test[mid]==target){ printf("見つかりました\n"); return 0; }         //大きい場合         else if(test[mid]<target){ left=mid+1; }         //小さい場合         else if(test[mid]>target){ right=mid-1; } } printf("見つかりませんでした\n"); return 0;



Comments