アルゴリズムとデータ構造 - 二分探索法の応用
二分探索法
基本概念
二分探索法は情報科学で広く応用されるアルゴリズムの一つです。その核心的なアイデアは各操作で半分の候補を除外することであり、これにより問題の解を \(\text{log}_2n\)（情報科学では通常 \(\text{log}n\) と表記）の操作回数で見つけることができます。
補足：アルゴリズムの計算量
コンピュータは十分速いかもしれないが、無限速ではない。——『 ...
5月25日 17:27 投稿
C言語における挿入ソートの仕組みと最適化実装
挿入ソートの基本概念
C言語における挿入ソート（Insertion Sort）は、小規模なデータや部分的に整列済みのデータに対して高い効率を発揮する整列アルゴリズムである。未整列の要素を順番に取り出し、既に整列済みの領域内で適切な挿入位置を後方から探索して挿入することで、全体の順序を構築していく仕組みを持つ。
標準的な挿入ソートの実装
以下に、挿入ソートの基本 ...
5月25日 04:03 投稿
河川の岩場問題：二分探索による最適解
問題リンク
https://www.luogu.org/problemnew/show/P2678
問題背景
年一度の「岩場飛び」大会が開催されます！
問題説明
この大会は一直線の川で行われ、川の中には大きな岩が点在しています。主催者はすでに2つの岩をスタート地点とゴール地点として選定しました。スタートとゴールの間にはN個の岩（スタートとゴールを含まない）があります。競技中、参加者はスター ...
5月19日 12:57 投稿
C言語の基礎演習問題
1.整数の階乗を計算する。
#include<stdio.h>
int main()
{
int i =1;
int n=0;
int ret=1;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
ret=ret*i;
}
printf("%d",ret);
return 0;
}
2.1!+2!+3!+4!+5!+6!+...+10!の和を求める。
#include<stdio.h>
int main()
{
int i =1;
int n=0;
int j=1;
for(j=1;j<=10;j ...
5月19日 00:14 投稿
Go言語による配列操作アルゴリズムの実装：二分探索と双指针法の応用
二分探索の境界条件設計
二分探索は、ソート済みのデータ構造から特定の要素を対数時間で検索するための基盤技術である。実装上の最も重要な要素は、探索区間の定義とループ継続条件の整合性を取り持つことにある。区間の表現方法により、実装パターンは大きく二つに分類される。
一つ目は両端を含む閉区間 `[lo, hi]` を採用する手法である。この場合、左端ポインタが右端 ...
5月18日 02:58 投稿
アルゴリズム入門：検索、グラフ探索、動的計画法、ハッシュ
検索アルゴリズム
データ集合から特定の要素を見つける操作です。代表的なものに線形探索と二分探索があります。
線形探索: 先頭から順番に各要素を比較し、目的の値が見つかるか、リストの終端に達するまで繰り返します。時間計算量はO(n)です。
二分探索: ソート済みの配列に対して使用されます。探索範囲の中間点の値と目的の値を比較し、探索範囲を半分ずつ狭めていき ...
5月17日 23:06 投稿
二つのソート済み配列の中央値の効率的な探索
問題概要
二つの昇順にソートされた整数配列 nums1 と nums2 が与えられます。それぞれの配列のサイズは m と n です。これら二つの配列を結合した場合の中央値を求めてください。
このアルゴリズムの時間計算量は O(log (m+n)) である必要があります。
例1:
入力：nums1 = [1,3], nums2 = [2]
出力：2.00000
解説：結合配列 = [1,2,3] 、中央値 2
アプローチ1：マージ ...
5月16日 05:19 投稿
配列内のピーク要素を対数時間で特定する二分探索アルゴリズムの実装
問題の定義と制約条件
隣接する要素よりも厳密に大きい値を「ピーク」と定義する。配列の両端（インデックス -1 および n）は負の無限大と見なせるため、配列内には必ず少なくとも1つのピークが存在することが数学的に保証されている。複数のピークが混在する可能性があるが、要件としていずれか1つのインデックスを返せば十分である。重要な制約として、線形探索ではなく ...
5月15日 04:44 投稿