C#の再帰処理で回転されたソート済み配列から要素を検索する方法

概要

回転されたソート済み配列（ローテート・ソート配列）から特定の値を検索するには、通常の二分探索を少し改良した再帰的なアプローチが有効です。ポイントは、中央の要素（最小要素）のインデックスを基準に配列を2つの部分に分け、どちら側に目的の値が存在するかを判定しながら探索範囲を絞り込んでいくことです。

アルゴリズムの手順

• 中央要素（最小要素）のインデックスを見つける。
• 以下の条件に基づいて、該当する部分配列に対して二分探索を適用する。
• 検索対象の値が開始要素から mid-1 番目の要素の間に存在する場合、start ～ mid-1 の範囲で二分探索を再帰的に実行する。
• それ以外で、値が mid ～ 末尾の要素の間に存在する場合は、mid+1 ～ end の範囲で二分探索を再帰的に実行する。

この方法により、たとえ配列が途中で回転していても、各ステップで必ず片側の半分は正しくソートされているため、O(log n) の時間計算量で効率よく値を検索できます。

サンプルコード

using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;
namespace ConsoleApplication{
    public class Arrays{
        public int FindNumberRotated(int[] array, int start, int end, int value){
            if (start > end){
                return -1;
            }
            int mid = (start + end) / 2;
            if (array[mid] == value){
                return mid;
            }
            if (array[start] <= array[mid]){
                if (value >= array[start] && value <= array[mid]){
                    return FindNumberRotated(array, start, mid - 1, value);
                }
                return FindNumberRotated(array, mid + 1, end, value);
            }
            if (value >= array[mid] && value <= array[end]){
                return FindNumberRotated(array, mid + 1, end, value);
            }
            return FindNumberRotated(array, start, mid - 1, value);
        }
    }
    class Program{
        static void Main(string[] args){
            Arrays a = new Arrays();
            int[] arr = { 3, 4, 5, 6, 7, 8, 9, 10, 1, 2 };
            int res = a.FindNumberRotated(arr, 0, arr.Length - 1, 1);
            Console.WriteLine(res);
        }
    }
}

実行結果

8

コードの解説

上記の例では、{ 3, 4, 5, 6, 7, 8, 9, 10, 1, 2 } という、元々昇順にソートされていた配列が途中で回転している状態を扱っています。FindNumberRotated メソッドは再帰的に呼び出され、まず中央要素と比較し、左半分がソート済みかどうか（array[start] <= array[mid]）を判定します。ソート済みの側に目的の値が含まれる範囲であればそこを探索し、含まれない場合は反対側へ探索範囲を移します。値が見つかればそのインデックスを返し、見つからなければ -1 を返します。この例では値「1」はインデックス 8 に存在するため、結果として 8 が出力されます。