%=====================================================================
% 秋田高専 2E 情報工学概論 テキスト
%　　テーマ　サーチ
%    本テキストの内容
%        ・
%        ・
%        ・
%        ・
%　　　 　・
%
% last updated 2005.11.13
%    created by  Masashi Yamamoto
%     e-mail yamamoto@akita-nct.jp
%=====================================================================
\documentclass[10pt,a4paper]{jarticle}
\usepackage{graphicx,amsmath,amssymb,ascmac,float}
\usepackage{html, listings, jlisting}
\oddsidemargin 0mm  %左の余白 25.4mm-0mm　奇数ページ
\evensidemargin 0mm %左の余白 25.4mm-0mm　偶数ページ
\textwidth 160mm
\newcommand{\command}[1]{「\texttt{#1}」}
\newcommand{\cl}[1]{\texttt{#1}}
\newcommand{\tw}[1]{\texttt{#1}}
%
\newcounter{toi_num}
\newcommand{\toi}{\textbf{\texttt [問\arabic{toi_num}]}
   \addtocounter{toi_num}{1}}
\newcommand{\qbox}[1]{
    {\fboxsep=2pt\fboxrule=0.4pt\fbox{\hspace{3mm}{#1}\hspace{3mm}}}
}
%
\renewcommand{\lstlistingname}{リスト}
\lstset{language=C,%
        basicstyle=\footnotesize,%
        commentstyle=\textit,%
        classoffset=1,%
        keywordstyle=\bfseries,%
	frame=tRBl,framesep=5pt,%
	showstringspaces=false,%
        numbers=left,stepnumber=1,numberstyle=\footnotesize%
	}%
%
\begin{htmlonly}
\usepackage{verbatimfiles}
 \providecommand{\lstinputlisting}[2][]{\verbatimlisting{#2}}
\end{htmlonly}
%
\begin{document}
\title{サーチ}
\author{山本昌志\thanks{独立行政法人　秋田工業高等専門学校　電気情報工学科}}
\date{2005年11月14日}
\maketitle
%
%
%=====================================================================
\section{前回の復習と本日の学習内容}
%=====================================================================
%---------------------------------------------------------------------
\subsection{前回の復習}
%---------------------------------------------------------------------
前回までは，データを並び替えるソートについて学習した．学習したソートのアルゴリズ
ムは，バブルソート，クイックソート，マージソート，コームソート，単純挿入ソート，
2分挿入ソートである．
%
%---------------------------------------------------------------------
\subsection{本日の学習内容}
%---------------------------------------------------------------------
本日は，サーチ(search:探索あるいは検索)について学習する．教科書~\cite{text_algorithm_data}に書いてあるとお
り，サーチとは，
\begin{quote}
 文字どおりたくさんのデータの中から目的のデータがどこにあるか(もしくは，あるかな
 いか)を調べる作業です．
\end{quote}
である．本日の講義では，整数のデータが配列に格納されている場合について，サーチを
学ぶ．どこにあるかは，配列の添え字で示すことになる．

サーチの方法はいろいろがあるが，ここでは，
\begin{itemize}
 \item リニアサーチ
 \item バイナリーサーチ
\end{itemize}
について学習する．
%
%=====================================================================
\section{リニアサーチ}
%=====================================================================
リニアサーチ(linear search)は，逐次検索あるは順検索(sequential search)とも呼ばれ，
配列などに格納されたデータを一つ一つ順に端から調べるだけの，素朴な方法である．
%---------------------------------------------------------------------
\subsection{単純な方法}
%---------------------------------------------------------------------
%-------------------
\subsubsection{原理}
%-------------------
原理は簡単で，配列の端から比較を行い，目的の整数を捜しているだけである．もう少し
詳しい説明は，教科書に書かれている．もし，配列が整理されておらずランダムに並んで
いる場合，この方法しか無い．

このリニアサーチの計算量のオーダーを考えよう．単純なリニアサーチのプログラムは，
教科書のList 2-1(p.37)に示されているとおりで，同じものをプリントのリスト
\ref{prog:list_1}に載せてある．このプログラムで，もっとも多く実行される，すなわ
ちもっとも多くの時間がかかる命令は，リスト\ref{prog:list_1}の13行目
\begin{quote}
 \setlength{\baselineskip}{12pt}
 \begin{verbatim}
	n<num&&a[n]!=x
 \end{verbatim}
\end{quote}\vspace{-3mm}
である．もし，$n$個のデータがあり，その中に目的のデータ(キー)がある場合，この命
令の平均実行回数は$n/2$である．データの中にキーが無い場合，$n$回，その命令は実行
される．データの中にキーの有無で平均実行回数は変わるが，いずれにしても計算量のオー
ダーは$O(n)$である．
%
%----------------------------
\subsubsection{フローチャート}
%----------------------------
教科書のList 2-1(p.37)あるいはこのプリントのリスト\ref{prog:list_1}のプログラム
のフローチャートを図\ref{fig:flow_1}に示す．
%
\begin{figure}[H]
 \begin{center}
  \includegraphics[keepaspectratio,scale=1.0]
  {figure/flow_1.eps}
  \caption{単純なリニアサーチのフローチャート．}
  \label{fig:flow_1}
 \end{center}
\end{figure}
%
%------------------------
\subsubsection{プログラム}
%------------------------
単純なリニアサーチのプログラムをリスト\ref{prog:list_1}に示す．これは，教科
書のList 2-1(p.37-38)と同じである．
%
\lstinputlisting[caption=リニアサーチ,label=prog:list_1]
{program/list2-1e.c}
%
%---------------------------------------------------------------------
\subsection{番兵を使う方法}
%---------------------------------------------------------------------
%-------------------
\subsubsection{原理}
%-------------------
最初に示したリスト\ref{prog:list_1}のプログラムは，ちょっとした工夫で実行速度を
向上させることができる．リスト\ref{prog:list_1}のもっとも計算時間がかかる13行目
は，2つの比較(\tw{n<num}と\tw{a[n]!=x})を行っている．キーを配列の最後に入れる(番
兵)ことにより，\tw{n<num}の比較の計算を行わないで済むようにできる．こうすると配
列の最後では，\tw{a[n]!=x]}が成立しなくなるので，ループから抜けることになる．ルー
プから抜けた後，キーと元々あった配列の最後の値と比較すればよいのである．

このようにすると，比較の数が半分になる．しかし，計算量のオーダーは$O(n)$と変わら
ないことに注意しよう．
%
%----------------------------
\subsubsection{フローチャート}
%----------------------------
番兵を使うリニアサーチのプログラムである教科書のList 2-2(p.38-39)あるいはこのプ
リントのリスト\ref{prog:list_2}のプログラムのフローチャートを図\ref{fig:flow_2}
に示す．番兵をどのように処理しているか，理解せよ．
%
\begin{figure}[H]
 \begin{center}
  \includegraphics[keepaspectratio,scale=1.0]
  {figure/flow_2.eps}
  \caption{番兵を使うリニアサーチのフローチャート．}
  \label{fig:flow_2}
 \end{center}
\end{figure}
%
%------------------------
\subsubsection{プログラム}
%------------------------
番兵を使うリニアサーチのプログラムをリスト\ref{prog:list_2}に示す．これは，教科
書のList 2-2(p.38-39)と同じである．
%
\lstinputlisting[caption=リニアサーチ．番兵を使う方法．,label=prog:list_2]
{program/list2-2e.c}
%
%=====================================================================
\section{バイナリーサーチ}
%=====================================================================
リニアサーチの欠点は，計算時間がかかることである．データの並びに規則性が無い場合，
リニアサーチのように端から順に捜すしかない．しかし，データの並びに規則性がある場
合，その性質を利用できる．

たとえば，データが昇順に並んでいた場合，端から比較するのではなく，最初に真ん中に位置す
るデータと比較する．すると，サーチするデータの個数がいっぺんに半分になる．同じこ
とを繰り返すと，比較すべき対象が$1/2$ずつ減少する．データの個数が多い場合，この
方法は劇的にサーチが早くなる．この方法をバイナリーサーチと言う．

リニアサーチだと，1回の比較で1個しかデータの候補が減らないのに，バイナリーサーチ
だと$n/2$個減少させることができるのである．ただし，バイナリーサーチを使うために
は，データを予めソートしておく必要がある．サーチの回数が1回であれば，ソートの手
間を考えるとリニアサーチの方が良い．サーチの回数が増加すると，バイナリーサーチの
方が有利になる．
%
%---------------------------------------------------------------------
\subsection{通常の方法}
%---------------------------------------------------------------------
%-------------------
\subsubsection{原理}
%-------------------
原理は単純で，データが昇順に並んでいる場合を考えれば理解できる．キーのある範囲を
$[left,right]$とする．これは，配列\tw{a[left]}と\tw{a[right]}の間が候補で，
この中にキーがある可能性があるということである．この範囲外には，キーと一致するデー
タは絶対に無いのである．データが$n$個ある場合，\tw{a[0]}から\tw{a[n-1]}
の範囲が候補なので，$[0,n-1]$の間にあると表現するのである．

つぎに，$mid=(left+right)/2$とキー\tw{x}を比較する．この比較の結果，
\begin{itemize}
 \item \tw{a[mid]}とキー\tw{x}が等しければ，キー\tw{x}のある位置は$mid$である．
 \item \tw{a[mic]}がキー\tw{x}よりも小さければ，$[mid+1,right]$にキー\tw{x}と一
       致するデータがある可能性がある．
 \item \tw{a[mic]}がキー\tw{x}よりも大きければ，$[left,mid-1]$にキー\tw{x}と一
       致するデータがある可能性がある．
\end{itemize}
が言える．これを繰り返すことにより，キーと一致するデータのある場所を捜す．

1回の計算，リスト\ref{prog:list_3}の12〜22行のループで，検索する範囲は$1/2$にな
る．したがって，$\alpha$回のループでその範囲が1になれば計算が終了する．データの
個数を$n$として，式で表すと，
\begin{align}
 n\left(\frac{1}{2}\right)^{\alpha}=1
\end{align}
となる．これから，計算回数$\alpha$は，
\begin{align}
 \alpha=\log_2 n
\end{align}
と導き出せる．バイナリーサーチの場合の計算量のオーダーは，$O(\log_2 n)$である．
%
%----------------------------
\subsubsection{フローチャート}
%----------------------------
単純なバイナリーサーチのプログラムである教科書のList 2-3(p.41-42)あるいはこのプ
リントのリスト\ref{prog:list_3}のプログラムのフローチャートを図\ref{fig:flow_3}
に示す．
%
\begin{figure}[H]
 \begin{center}
  \includegraphics[keepaspectratio,scale=1.0]
  {figure/flow_3.eps}
  \caption{単純なバイナリーサーチ．}
  \label{fig:flow_3}
 \end{center}
\end{figure}
%
%------------------------
\subsubsection{プログラム}
%------------------------
単純なバイナリーサーチのプログラムをリスト\ref{prog:list_3}に示す．これは，教科
書のList 2-3(p.41-42)と同じである．
%
\lstinputlisting[caption=バイナリーサーチ．,label=prog:list_3]
{program/list2-3e.c}
%
%---------------------------------------------------------------------
\subsection{先頭を返す方法}
%---------------------------------------------------------------------
%-------------------
\subsubsection{原理}
%-------------------
キーと一致するデータが複数ある場合，ソートされているので，それらは配列で同じ値が
続くことになる．この場合，リスト\ref{prog:list_3}だとそれらのうち最初に一致した
位置を返すことになる．どれに一致するかは，データに依存する．このように複数と一致
する場合は，その先頭の位置を知りたいことがある．

このように，先頭を知りたい場合は必ずとなり通しと比較するようにすればよい．そのよ
うにするためには，\ref{prog:list_3}を改良して，\ref{prog:list_4}のようにすれば良
い．
%
%----------------------------
\subsubsection{フローチャート}
%----------------------------
同じ値が続く場合にその先頭の位置を返すバイナリーサーチのプログラムである教科書の
List 2-4(p.44-45)あるいはこのプリントのリスト\ref{prog:list_4}のフローチャートを
図\ref{fig:flow_4} に示す．
%
\begin{figure}[H]
 \begin{center}
  \includegraphics[keepaspectratio,scale=1.0]
  {figure/flow_4.eps}
  \caption{一致する配列の先頭を返すバイナリーサーチのフローチャート．}
  \label{fig:flow_4}
 \end{center}
\end{figure}
%
%------------------------
\subsubsection{プログラム}
%------------------------
一致するデータが複数の場合，もっとも先頭に近い位置を返すバイナリーサーチのプログラムをリスト\ref{prog:list_4}に示す．これは，教科
書のList 2-4(p.44-45)と同じである．
%
\lstinputlisting[caption=バイナリーサーチ．同じ値が続く場合にその先頭の位置を返す．,label=prog:list_4]
{program/list2-4e.c}
%
%=====================================================================
\section{課題}
%=====================================================================
%---------------------------------------------------------------------
\subsection{課題内容}
%---------------------------------------------------------------------
%----------------------------
\subsubsection{リニアサーチ}
%---------------------------
以下の数列のリニアサーチに関する問題である．
%
\begin{quote}
 \begin{small}
  \begin{verbatim}
752 778	608 239 956 244 535 840 629 353
  \end{verbatim}
 \end{small}
\end{quote}
%
\setcounter{toi_num}{1}
\begin{quote}
 \begin{itemize}
  \item[\toi]リスト\ref{prog:list_1}で，535を捜す場合の比較の対象を順に示せ．
  \item[\toi]リスト\ref{prog:list_1}で，643を捜す場合の比較の対象を順に示せ．
  \item[\toi]リスト\ref{prog:list_2}で，535を捜す場合の比較の対象を順に示せ．
  \item[\toi]リスト\ref{prog:list_2}で，643を捜す場合の比較の対象を順に示せ．
 \end{itemize}
\end{quote}
%----------------------------
\subsubsection{バイナリーサーチ}
%---------------------------
以下の数列のバイナリーサーチに関する問題である．
%
\begin{quote}
 \begin{small}
  \begin{verbatim}
239 244 353 535 608 629 752 752 752 956  
  \end{verbatim}
 \end{small}
\end{quote}
%
\setcounter{toi_num}{1}
\begin{quote}
 \begin{itemize}
  \item[\toi]リスト\ref{prog:list_3}で，650を捜す場合の比較の対象を順に示せ．
  \item[\toi]リスト\ref{prog:list_3}で，752を捜す場合の比較の対象を順に示せ．
  \item[\toi]リスト\ref{prog:list_4}で，650を捜す場合の比較の対象を順に示せ．
  \item[\toi]リスト\ref{prog:list_4}で，752を捜す場合の比較の対象を順に示せ．
 \end{itemize}
\end{quote}
%---------------------------------------------------------------------
\subsection{レポート提出要領}
%---------------------------------------------------------------------
提出方法は、次の通りとする。
% 
\begin{quote}
 \begin{tabular}{ll}
  期限 & 11月21日(月) AM 10:40 \\
  用紙 & A4 \\
  提出場所 & 山本研究室の入口のポスト \\
  表紙 & 表紙を1枚つけて、以下の項目を分かりやすく記述すること。\\
       & \qquad 授業科目名「情報工学」\\
       & \qquad 課題名「課題　サーチ」\\
       & \qquad 2E\quad 学籍番号\quad 氏名\\
       & \qquad 提出日\\
  内容 & 2ページ以降に問いに対する答えを分かりやすく記述すること．
 \end{tabular}
\end{quote}
%=====================================================================
%  参考文献
%=====================================================================
\bibliographystyle{jplain}
\bibliography{reference}
%=====================================================================
\end{document}