C LANGUAGE TECHNOLOGY

【C言語】線形探索と二分探索で数値と文字列の検索【lfind/lsearch/bsearch関数と自作関数】

2021年10月1日

悩んでいる人

C言語で線形探索と二分探索を教えて!

こういった悩みにお答えします.

本記事の信頼性

  • リアルタイムシステムの研究歴12年.
  • 東大教員の時に,英語でOS(Linuxカーネル)の授業.
  • 2012年9月~2013年8月にアメリカのノースカロライナ大学チャペルヒル校(UNC)コンピュータサイエンス学部で客員研究員として勤務.C言語でリアルタイムLinuxの研究開発.
  • プログラミング歴15年以上,習得している言語: C/C++PythonSolidity/Vyper,Java,Ruby,Go,Rust,D,HTML/CSS/JS/PHP,MATLAB,Assembler (x64,ARM).
  • 東大教員の時に,C++言語で開発した「LLVMコンパイラの拡張」,C言語で開発した独自のリアルタイムOS「Mcube Kernel」GitHubにオープンソースとして公開
  • 2020年1月~現在はアメリカのノースカロライナ州チャペルヒルにあるGuarantee Happiness LLCのCTOとしてECサイト開発やWeb/SNSマーケティングの業務.2022年6月~現在はアメリカのノースカロライナ州チャペルヒルにあるJapanese Tar Heel, Inc.のCEO兼CTO.
  • 最近は自然言語処理AIイーサリアムに関する有益な情報発信に従事.
    • (AI全般を含む)自然言語処理AIの論文の日本語訳や,AIチャットボット(ChatGPT,Auto-GPT,Gemini(旧Bard)など)の記事を50本以上執筆.アメリカのサンフランシスコ(広義のシリコンバレー)の会社でプロンプトエンジニア・マネージャー・Quality Assurance(QA)の業務委託の経験あり.
    • (スマートコントラクトのプログラミングを含む)イーサリアムや仮想通貨全般の記事を200本以上執筆.イギリスのロンドンの会社で仮想通貨の英語の記事を日本語に翻訳する業務委託の経験あり.

こういった私から学べます.

C言語を独学で習得することは難しいです.

私にC言語の無料相談をしたいあなたは,公式LINE「ChishiroのC言語」の友だち追加をお願い致します.

私のキャパシティもあり,一定数に達したら終了しますので,今すぐ追加しましょう!

友だち追加

独学が難しいあなたは,元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう.後悔はさせません!

線形探索と二分探索

線形探索とは,n個の配列のデータを前から(または後ろから)順番に検索する探索アルゴリズムです.

線形探索の最悪計算量は\(\mathcal{O}(n)\)です.

これに対して,二分探索とは,ソート済み配列(またはリスト)のデータに対する探索アルゴリズムです.

ここで,二分探索ではソート済みの配列に入ったデータ(同一の値はなくユニークと仮定する)に対する検索を行います.

検索範囲の中央の値を見て,検索したい値との大小関係を比較します.

検索したい値が中央の値の右にあるか左にあるかを判断し,片側には存在しないことを確かめながら検索範囲を狭めていくことで,検索する値があるかどうかを判定します.

二分探索は大小関係を利用するため,未ソートや大小関係の定義されない要素を含む配列には利用できないことに注意して下さい.

二分探索の最悪計算量は\(\mathcal{O}(\log_2 n)\)です.

線形探索と比較して,二分探索は要素の数が多いほど効果的な探索アルゴリズムと言えます.

線形探索と二分探索の標準ライブラリ関数

線形探索と二分探索の標準ライブラリ関数を紹介します.

lfind/lsearch関数

lfind/lsearch関数は,sizeバイトの要素*nmemb個から構成される配列baseからkeyを線形検索する関数です.

比較を行うのはcompar関数ポインタが参照している関数で,2つの引数を持ち,第1引数はkey,第2引数は配列の要素を指します.

compar関数ポインタは,keyが配列の要素と一致した場合は0,そうでなければ0以外を返す必要があります.

lsearch関数は,一致する要素を見つけられなかったとき,配列の最後にkeyを追加し,*nmemb を1増やします.

したがって,この関数を使用する際には,一致する要素が存在するか,もしくは配列に要素を追加するための領域があるかを事前に確認する必要があることに注意して下さい.

lfind関数の返り値は,配列の一致した要素へのポインタです.一致する要素が見つからない場合はNULLを返します.

lsearch関数の返り値も,配列の一致した要素へのポインタです.一致する要素が見つからなかった場合は,新たに追加した要素へのポインタを返します.

※lfind/lsearch関数の仕様を勘違いしやすいので注意して下さい.

bsearch関数

bsearch関数は,nmemb個の要素からなる配列を二分探索する関数です.

配列の最初の要素へのポインタはbaseで指定します.

ポインタkeyで参照される値と一致する要素が返されます.

配列中の各々の要素のサイズはsizeで指定します.

配列の内容はcompar関数ポインタに基づき,昇順にソートされていなければなりません.

comparの第1引数はkeyへのポインタ,第2引数は配列の要素へのポインタです.

keyが配列の要素より小さい場合は負の整数,大きい場合は正の整数を,一致した場合は0を返す必要があります.

bsearch関数は,配列の要素で一致したものへのポインタを返します.見つからなかった場合はNULLを返します.

keyと一致した要素が複数ある場合,どの要素が返されるかは未定義(実装依存)です.

線形探索で数値を検索

線形探索で数値を検索するコードを紹介します.

lfind関数で数値を検索

lfind関数で数値を検索するコードは以下になります.

実行結果は以下になります.

4行目の行末で11を入力したらarray[0]で発見できたこと,8行目の行末で1を入力したら発見できなかったことがわかります.

lsearch関数で数値を検索

lsearch関数で数値を検索するコードは以下になります.

実行結果は以下になります.

4行目の行末で11を入力したらarray[0]で発見できたこと,9行目の行末で1を入力したら発見できなかったため,11行目で1を配列の最後に追加したことがわかります.

線形探索の自作関数で数値を検索

線形探索の自作関数で数値を検索するコードは以下になります.

実行結果は以下になります.

線形探索で文字列を検索

線形探索で文字列を検索するコードを紹介します.

lfind関数で文字列を検索

lfind関数で文字列を検索するコードは以下になります.

実行結果は以下になります.

4行目の行末でabcを入力したらarray[0]で発見できたこと,9行目の行末でeを入力したら発見できなかったことがわかります.

lsearch関数で文字列を検索

lsearch関数で文字列を検索するコードは以下になります.

実行結果は以下になります.

線形探索の自作関数で文字列を検索

線形探索の自作関数で文字列を検索するコードは以下になります.

実行結果は以下になります.

二分探索で数値を検索

二分探索で数値を検索するコードを紹介します.

bsearch関数で数値を検索

bsearch関数で数値を検索するコードは以下になります.

実行結果は以下になります.

4行目の行末で11を入力したらarray[3]で発見できたこと,8行目の行末で1を入力したら発見できなかったことがわかります.

二分探索の自作関数で数値を検索

二分探索の自作関数で数値を検索するコードは以下になります.

実行結果は以下になります.

二分探索で文字列を検索

二分探索で文字列を検索する方法を紹介します.

bsearch関数で文字列を検索

bsearch関数で文字列を検索するコードは以下になります.

実行結果は以下になります.

4行目の行末でabcを入力したらarray[1]で発見できたこと,8行目の行末でeを入力したら発見できなかったことがわかります.

二分探索の自作関数で文字列を検索

二分探索の自作関数で文字列を検索するコードは以下になります.

qsort関数を利用していますので,使い方を知りたいあなたはこちらからどうぞ.

実行結果は以下になります.

まとめ

C言語の線形探索と二分探索で数値と文字列を検索する方法を紹介しました.

両方ともよく利用するので,きちんと理解しておきましょう.

ハッシュテーブルを利用したハッシュ検索を知りたいあなたはこちらからどうぞ.

文字列を検索するstrstr関数や文字列検索アルゴリズムを知りたいあなたはこちらからどうぞ.

C言語を独学で習得することは難しいです.

私にC言語の無料相談をしたいあなたは,公式LINE「ChishiroのC言語」の友だち追加をお願い致します.

私のキャパシティもあり,一定数に達したら終了しますので,今すぐ追加しましょう!

友だち追加

独学が難しいあなたは,元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう.後悔はさせません!

-C LANGUAGE, TECHNOLOGY
-, , , , , , ,