%=====================================================================
% ���Ĺ��� 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}
