ヽ｜∵｜ゝ(Fantom) の 開発blog？

using System.Collections.Generic;

public static class Extentions  //※名前は任意
{
    /// <summary>
    /// 昇順で要素を追加する
    /// 2021/02/02 Fantom
    /// http://fantom1x.blog130.fc2.com/blog-entry-392.html
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="list">対象リスト</param>
    /// <param name="value">追加する要素</param>
    /// <returns>true = 新規追加 / false = 既存あり(重複で追加)</returns>
    public static bool AddSorted<T>(this List<T> list, T value)
    {
        int idx = list.BinarySearch(value);
        if (idx < 0)
        {
            list.Insert(~idx, value);
            return true;
        }
        list.Insert(idx, value);
        return false;
    }

    /// <summary>
    /// 昇順で要素をユニーク追加する
    /// 2021/02/02 Fantom
    /// http://fantom1x.blog130.fc2.com/blog-entry-392.html
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="list">対象リスト</param>
    /// <param name="value">追加する要素</param>
    /// <returns>true = 新規追加 / false = 既存あり(追加しない)</returns>
    public static bool AddSortedUniq<T>(this List<T> list, T value)
    {
        int idx = list.BinarySearch(value);
        if (idx < 0)
        {
            list.Insert(~idx, value);
            return true;
        }
        return false;
    }

    /// <summary>
    /// 昇順のリストから要素を削除
    /// 2021/02/02 Fantom
    /// http://fantom1x.blog130.fc2.com/blog-entry-392.html
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="list">対象リスト</param>
    /// <param name="value">削除する要素</param>
    /// <returns>true = 削除した / false = 既存なし(削除失敗)</returns>
    public static bool RemoveSorted<T>(this List<T> list, T value)
    {
        int idx = list.BinarySearch(value);
        if (idx >= 0)
        {
            list.RemoveAt(idx);
            return true;
        }
        return false;
    }
}

using System;
using System.Collections.Generic;

string[] array =
{
    "Apple", "Banana", "Candy", "Donuts", "Egg", "Fish", "Candy", "Egg"
};

array.Shuffle();  //※Shuffle は以前の記事を参照
Console.WriteLine(array.Dump());  //※Dump は以前の記事を参照

var list1 = new List(array.Length);
var list2 = new List(array.Length);
foreach (var item in array)
{
    list1.AddSorted(item);      //昇順で追加
    list2.AddSortedUniq(item);  //昇順でユニーク追加
}

Console.WriteLine("list1 : " + list1.Dump());  //※Dump は以前の記事を参照
Console.WriteLine("list2 : " + list2.Dump());  //※Dump は以前の記事を参照

//昇順リストから削除
list1.RemoveSorted("Candy");
list1.RemoveSorted("Egg");
Console.WriteLine("list1 (Removed) : " + list1.Dump());  //※Dump は以前の記事を参照
Console.WriteLine("list2 (Removed) : " + list2.Dump());  //※Dump は以前の記事を参照

//二分探索
int idx1 = list1.BinarySearch("Candy");
Console.WriteLine($"idx1 = {idx1}");
int idx2 = list1.BinarySearch("Egg");
Console.WriteLine($"idx2 = {idx2}");

using System;
using System.Collections.Generic;

/// <summary>
/// インデクスで範囲指定の二分探索
/// 2019/10/11 Fantom
/// http://fantom1x.blog130.fc2.com/blog-entry-338.html
/// </summary>
/// <typeparam name="T">比較する値の型</typeparam>
/// <param name="arr">対象の配列（※ソート済みであること）</param>
/// <param name="start">開始インデクス [inclusive]</param>
/// <param name="end">終了インデクス [exclusive]</param>
/// <param name="value">検索する値</param>
/// <param name="comparer">比較関数(インターフェイス)</param>
/// <returns>0 以上のとき見つかったインデクス / 0 より小さいとき ~index (ビット反転)で挿入位置になる</returns>
public static int BinarySearch<T>(this List<T> list, int start, int end, T value, IComparer<T> comparer)
{
    int low = start;
    int high = end - 1;
    int mid;
    while (low <= high)
    {
        mid = ((high - low) >> 1) + low;
        if (comparer.Compare(list[mid], value) < 0)
        {
            low = mid + 1;
        }
        else if (comparer.Compare(list[mid], value) > 0)
        {
            high = mid - 1;
        }
        else
        {
            return mid;
        }
    }
    return -(low + 1);
}

//引数省略のオーバーロード
public static int BinarySearch<T>(this List<T> list, int start, int end, T value)
{
    return BinarySearch(list, start, end, value, Comparer<T>.Default);
}

using System;
using System.Collections.Generic;

/// <summary>
/// 指定した値以上の先頭のインデクスを返す (二分探索)
/// 2017/08/04 Fantom
/// http://fantom1x.blog130.fc2.com//blog-entry-256.html
/// </summary>
/// <typeparam name="T">比較する値の型</typeparam>
/// <param name="arr">対象の配列（※ソート済みであること）</param>
/// <param name="start">開始インデクス [inclusive]</param>
/// <param name="end">終了インデクス [exclusive]</param>
/// <param name="value">検索する値</param>
/// <param name="comparer">比較関数(インターフェイス)</param>
/// <returns>指定した値以上の先頭のインデクス</returns>
public static int LowerBound<T>(T[] arr, int start, int end, T value, IComparer<T> comparer)
{
    int low = start;
    int high = end;
    int mid;
    while (low < high)
    {
        mid = ((high - low) >> 1) + low;
        if (comparer.Compare(arr[mid], value) < 0)
            low = mid + 1;
        else
            high = mid;
    }
    return low;
}

//引数省略のオーバーロード
public static int LowerBound<T>(T[] arr, T value) where T : IComparable
{
    return LowerBound(arr, 0, arr.Length, value, Comparer<T>.Default);
}

/// <summary>
/// 指定した値より大きい先頭のインデクスを返す (二分探索)
/// 2017/08/04 Fantom
/// http://fantom1x.blog130.fc2.com//blog-entry-256.html
/// </summary>
/// <typeparam name="T">比較する値の型</typeparam>
/// <param name="arr">対象の配列（※ソート済みであること）</param>
/// <param name="start">開始インデクス [inclusive]</param>
/// <param name="end">終了インデクス [exclusive]</param>
/// <param name="value">検索する値</param>
/// <param name="comparer">比較関数(インターフェイス)</param>
/// <returns>指定した値より大きい先頭のインデクス</returns>
public static int UpperBound<T>(T[] arr, int start, int end, T value, IComparer<T> comparer)
{
    int low = start;
    int high = end;
    int mid;
    while (low < high)
    {
        mid = ((high - low) >> 1) + low;
        if (comparer.Compare(arr[mid], value) <= 0)
            low = mid + 1;
        else
            high = mid;
    }
    return low;
}

//引数省略のオーバーロード
public static int UpperBound<T>(T[] arr, T value)
{
    return UpperBound(arr, 0, arr.Length, value, Comparer<T>.Default);
}

//※・・・関数などは略・・・

//表の各要素の開始の風速を配列にしたもの
double[] WindPower = {
    0.0, 0.3, 1.6, 3.4, 5.5, 8.0, 10.8, 13.9, 17.2, 20.8, 24.5, 28.5, 32.7
};

double ms = 15.3; //※与えられた風速とする(m/s)
int wp = UpperBound(WindPower, ms) - 1;
Console.WriteLine("風速" + wp);

//※・・・関数などは略・・・

//表の各要素の開始の風速を配列にしたもの
double[] WindPower = {
    0.0, 0.3, 1.6, 3.4, 5.5, 8.0, 10.8, 13.9, 17.2, 20.8, 24.5, 28.5, 32.7
};

double ms = 15.3; //※与えられた風速とする(m/s)
int wp = Array.BinarySearch(WindPower, ms);
Console.WriteLine("風速" + (wp < 0 ? ~wp - 1 : wp)); //見つからなかったときビット反転（~）するとUpperBoundと同じになる

//※・・・関数などは略・・・

int[] arr = {0, 0, 1, 1, 1, 2, 2, 3, 4, 4, 4, 5, 5}; //表
int low  = 2; //検索する最小値
int high = 4; //検索する最大値
int from = LowerBound(arr, low); //検索する最小値で最初のインデクス
int to = UpperBound(arr, high);  //検索する最大値を超えた最初のインデクス
Console.WriteLine("from = " + from + ", to = " + to + ", count = " + (to - from));

     #[0][1][2][3][4][5][6][7][8][9[10[11[12[13[14]
arr = [1, 1, 3, 3, 3, 4, 5, 5, 6, 6, 6, 6, 7, 8, 8];
v = 3;
lower = arr.bsearch_index{|x| x >= v}  #lower_bound 的(ただし、見つからない=nil) (Ruby 2.3以降)
upper = arr.bsearch_index{|x| x > v}   #upper_bound 的(ただし、見つからない=nil) (Ruby 2.3以降)
print "lower = #{lower}\n"
print "upper = #{upper}\n"

#オープンクラス版
class Array
  #二分探索(同値連続はインデクス不定となる)
  #見つからないとき=負の値となり、~index で挿入位置になる
  def binary_search(value, from = 0, to = self.size)
    low = from
    high = to - 1
    while low <= high
      mid = (low + high) / 2
      if self[mid] < value
        low = mid + 1
      elsif self[mid] > value
        high = mid - 1
      else
        return mid
      end
    end
    -(low + 1) #見つからない(~index で挿入位置)
  end

  #指定した値以上の先頭のインデクスを返す
  def lower_bound(value, from = 0, to = self.size)
    low = from
    high = to
    while low < high
      mid = (low + high) / 2
      if self[mid] < value
        low = mid + 1
      else
        high = mid
      end
    end
    low
  end

  #指定した値より大きい先頭のインデクスを返す
  def upper_bound(value, from = 0, to = self.size)
    low = from
    high = to
    while low < high
      mid = (low + high) / 2
      if self[mid] <= value
        low = mid + 1
      else
        high = mid
      end
    end
    low
  end

end


#メインでは...
     #[0][1][2][3][4][5][6][7][8][9[10[11[12[13[14]
arr = [1, 1, 3, 3, 3, 4, 5, 5, 6, 6, 6, 6, 7, 8, 8];
v = 3;    #検索する値
print "binary_search = #{arr.binary_search(v)}\n"
print "lower_bound = #{arr.lower_bound(v)}\n"
print "upper_bound = #{arr.upper_bound(v)}\n"

print "bsearch_index(lower) = #{arr.bsearch_index{|x| x >= v}}\n"  #lower_bound 的(ただし、見つからない=nil) (Ruby 2.3)
print "bsearch_index(upper) = #{arr.bsearch_index{|x| x > v}}\n"  #upper_bound 的(ただし、見つからない=nil) (Ruby 2.3)

arr = [3, 5, 6, 4, 2, 0, 8, 7, 1, 9]
sorted = []

arr.each{|e|
  sorted.insert(sorted.upper_bound(e), e)

#  sorted.insert(sorted.lower_bound(e), e)

#  idx = sorted.binary_search(e)
#  if idx < 0
#    idx = ~idx
#  end
#  sorted.insert(idx, e)
}

p arr
p sorted

arr = [0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 6, 6, 6, 7, 8, 9, 9]

lo, hi = 1, 3   #検索する値の範囲
fr = arr.lower_bound(lo)  #開始インデクスを表す
to = arr.upper_bound(hi)  #終了インデクスを表す[このインデクスは含まない]

p arr
print "fr = #{fr}, to = #{to}, cnt = #{to - fr}\n"  #差分が個数
p arr.slice(fr, to - fr)  #範囲を抜き出し

#二分探索(同値連続はインデクス不定となる)
#見つからないとき=負の値となり、~index で挿入位置になる
def binary_search(arr, value, from = 0, to = arr.size)
  low = from
  high = to - 1
  while low <= high
    mid = (low + high) / 2
    if arr[mid] < value
      low = mid + 1
    elsif arr[mid] > value
      high = mid - 1
    else
      return mid
    end
  end
  -(low + 1) #見つからない(~index で挿入位置)
end

#指定した値以上の先頭のインデクスを返す
def lower_bound(arr, value, from = 0, to = arr.size)
  low = from
  high = to
  while low < high
    mid = (low + high) / 2
    if arr[mid] < value
      low = mid + 1
    else
      high = mid
    end
  end
  low
end

#指定した値より大きい先頭のインデクスを返す
def upper_bound(arr, value, from = 0, to = arr.size)
  low = from
  high = to
  while low < high
    mid = (low + high) / 2
    if arr[mid] <= value
      low = mid + 1
    else
      high = mid
    end
  end
  low
end


#メインでは...
     #[0][1][2][3][4][5][6][7][8][9[10[11[12[13[14]
arr = [1, 1, 3, 3, 3, 4, 5, 5, 6, 6, 6, 6, 7, 8, 8];
v = 3;    #検索する値

print "binary_search = #{binary_search(arr, v)}\n"
print "lower_bound = #{lower_bound(arr, v)}\n"
print "upper_bound = #{upper_bound(arr, v)}\n"

s, e = 3, 6    #検索する値の範囲
fr = lower_bound(arr, s)
to = upper_bound(arr, e)
print "fr = #{fr}, to = #{to}, cnt = #{to - fr}\n"

public interface ICondition {
    boolean condition(double x);
}

/**<h1>条件にあった値を二分探索で求める(実数)</h1>
 * <p>条件判別関数は、等しいかより値を大きくとるとき = true となる関数を作る。</p>
 * @param low ： 探索範囲下限
 * @param high ： 探索範囲上限
 * @param c ： 条件判別関数インターフェイス
 * @return<b>double</b> ： 探索で見つけた値
 */
public static final double binarySearch(double low, double high, final ICondition c) {
    double mid = 0;
    for (int i = 0; i < 100; i++) {    //無限ループ対策
        mid = (high - low) / 2 + low;    //(low + high) / 2 (オーバーフロー対策)
        if (c.condition(mid)) {
            low = mid;
        } else {
            high = mid;
        }
    }
    return low;
}


/**<h1>条件にあった値を二分探索で求める(整数)</h1>
 * <p>条件判別関数は、等しいかより値を大きくとるとき = true となる関数を作る。</p>
 * @param low ： 探索範囲下限
 * @param high ： 探索範囲上限
 * @param c ： 条件判別関数インターフェイス
 * @return<b>int</b> ： 探索で見つけた値
 */
public static final int binarySearch(int low, int high, final ICondition c) {
    int mid = 0;
    while (high - low > 1) {
        mid = ((high - low) >>> 1) + low;    //(low + high) / 2 (オーバーフロー対策)
        if (c.condition(mid)) {
            low = mid;
        } else {
            high = mid;
        }
    }
    return low;
}

public class BinarySearchTest {
    public static void main(String[] args) throws Exception {
        new BinarySearchTest();
    }

    double[] A;   //長さのリスト
    int N;        //リストの要素数
    int K;        //作る本数

    public BinarySearchTest() {
        A = new double[]{8.02, 7.43, 4.57, 5.39};
        N = A.length;
        K = 11;

        double ans = binarySearch(0.0, 1e5, new ICondition() {
            //・長さ x で K より多く切れるとき → もっと x を長くできる = true
            //・長さ x で K より少なく切れるとき → もっと x を短くする = false
            @Override
            public boolean condition(double x) {
                int cnt = 0;
                for (int i = 0; i < N; i++) {
                    cnt += (int)(A[i] / x);    //作れる本数
                }
                return (cnt >= K);
            }
        });

        System.out.println(ans);    //2.005
    }

    //※ binarySearch() 関数は省略
}

public class BinarySearchTest implements ICondition {
    public static void main(String[] args) throws Exception {
        new BinarySearchTest();
    }

    double[] A;   //長さのリスト
    int N;        //リストの要素数
    int K;        //作る本数

    public BinarySearchTest() {
        A = new double[]{8.02, 7.43, 4.57, 5.39};
        N = A.length;
        K = 11;

        double ans = binarySearch(0.0, 1e5, this);
        System.out.println(ans);    //2.005
    }

    //・長さ x で K より多く切れるとき → もっと x を長くできる = true
    //・長さ x で K より少なく切れるとき → もっと x を短くする = false
    @Override
    public boolean condition(double x) {
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            cnt += (int)(A[i] / x);    //作れる本数
        }
        return (cnt >= K);
    }

    //※ binarySearch() 関数は省略
}

double ans = binarySearch(0.0, 1.0, new ICondition() {
    //・x = 0 とすると、f(x) = 0、x = 1 とすると、f(x) = 3 から、x = 0.0～1.0 となる。
    //・f(x) の解が 1 以下のとき x はもっと大きい = true
    //・f(x) の解が 1 より上のとき x はもっと小さい = false
    @Override
    public boolean condition(double x) {
        return (x * x * x + x * x + x <= 1.0);
    }
});

System.out.println(ans);    //0.5436890126920764

//※ メインコード, binarySearch() 関数は省略

public class BinarySearchTest {
    public static void main(String[] args) throws Exception {
        new BinarySearchTest();
    }

    double price;            //ローン初期残高
    double monthlyPayment;   //月々の支払額
    int loanTerm;            //ローン回数

    public BinarySearchTest() {
        price = 2000;
        monthlyPayment = 510;
        loanTerm = 4;

        double ans = binarySearch(0.0, 100.0, new ICondition() {
            //・残高がマイナスになる → 利率を大きくする = true
            //・残高がプラスになる → 利率を小さくする = false
            @Override
            public boolean condition(double x) {
                double balance = price;
                for (int i = 0; i < loanTerm; i++) {
                    balance *= x / 1200.0 + 1.0;    //月々の利率
                    balance -= monthlyPayment;
                }
                return (balance <= 0);
            }
        });

        System.out.println(ans);    //9.56205462458368 (%) (※誤差あり)
    }

    //※ binarySearch() 関数は省略
}

public class BinarySearchTest {
    public static void main(String[] args) throws Exception {
        new BinarySearchTest();
    }

    int[] A;      //小屋の位置リスト
    int N;        //リストの要素数
    int M;        //配置する牛の数

    public BinarySearchTest() {
        A = new int[]{1, 3, 4, 6, 7, 10, 12, 15, 18, 20, 22, 23, 25, 27};
        N = A.length;
        M = 4;

        int ans = binarySearch(0, A[N - 1], new ICondition() {
            //・間隔 x で M 頭の牛が全て収まるとき → もっと x を大きくできる = true
            //・間隔 x で M 頭の牛が収まらないとき → もっと x を小さくする = false
            @Override
            public boolean condition(double x) {
                int now = 0;
                for (int i = 1; i < M; i++) {
                    int next = now + 1;
                    while (next < N && A[next] - A[now] < x) {
                        next++;
                    }
                    if (next == N) {
                        return false;    //M 頭まで配置できない
                    }
                    now = next;
                }
                return true;    //M 頭配置できる
            }
        });

        System.out.println(ans);    //8
    }

    //※ binarySearch() 関数は省略
}