C LANGUAGE TECHNOLOGY

【C言語】二分探索で数値と文字列の検索

悩んでいる人

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

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

本記事の信頼性

  • リアルタイムシステムの研究歴12年.
  • 東大教員の時に,英語でOSの授業.
  • 2012年9月~2013年8月にアメリカのノースカロライナ大学チャペルヒル校コンピュータサイエンス学部2021年の世界大学学術ランキングで20位)で客員研究員として勤務.C言語でリアルタイムLinuxの研究開発
  • プログラミング歴15年以上,習得している言語: C/C++Solidity,Java,Python,Ruby,HTML/CSS/JS/PHP,MATLAB,Assembler (x64,ARM).
  • 東大教員の時に,C++言語で開発した「LLVMコンパイラの拡張」,C言語で開発した独自のリアルタイムOS「Mcube Kernel」GitHubにオープンソースとして公開

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

二分探索

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

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

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

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

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

n個のデータがある場合,二分探索の計算量は\(\mathcal{O}(\log_2 n)\)です.

これに対して,配列のデータを前から(または後ろから)順番に検索する線形探索の計算量は\(\mathcal{O}(n)\)です.

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

本記事では,二分探索で数値と文字列を検索するコードを紹介していきます.

二分探索で数値を検索

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

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

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

二分探索で文字列を検索

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

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

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

まとめ

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

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

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

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

友だち追加

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

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