配列データ構造と基礎的なアルゴリズム手法の解説
配列の検索および演算テクニック
配列は連続したメモリ領域を使用する基本的なコレクションであり、インデックスによる高速アクセスが可能です。ここでは、配列を扱う際の代表的なアルゴリズムパターンとその実装について解説します。
1. 二分探索アルゴリズムの境界条件
ソートされた配列から特定の値を検索する際に、二分探索法が用いられます。実装上の注意点として、 ...
8月12日 23:48 投稿
アルゴリズム実践トレーニングカリキュラム
配列操作編
二分探索と要素削除
二分探索：境界条件の2つの実装方法に注意。rightの定義、if条件と境界更新ロジックが重要。
左閉右閉左閉右開
rightの定義len(arr) - 1len(arr)
ループ条件while left <= right:while left < right:
境界更新right = mid - 1right = mid
class Solution:
def binary_search(self, arr: List[int], target: int) -> int:
...
6月26日 18:36 投稿
数列の部分ソート後の指定位置値の特定
問題概要
1からnまでの順列に対してm回の部分ソート操作を実行し、q番目の位置にある数値を求める問題。ソート操作は昇順または降順のどちらかで、指定された区間内の要素を並び替える。
入力形式
n m
a_1 a_2 ... a_n
op_1 l_1 r_1
...
op_m l_m r_m
q
解法概要
二分探索とセグメント木を組み合わせたO(n log²n)のアルゴリズムを使用する。重要なのは「ある値Xより大 ...
5月22日 19:15 投稿