二分検索を実装するための Java コード例

この記事は主にJavaバイナリサーチの関連情報を紹介します

アルゴリズム

3、12、24、36、55、68、75の数字のセットがあるとします。 , 88 指定された値を確認するには 24. 3 つの 変数 front、mid、end をそれぞれデータの上限、中間、下限を指すように設定できます (mid=(front+end)/2)。

front=0 (3 を指す)、end=7 (88 を指す)、次に Mid=3 (36 を指す) で始まります。 Mid>x なので、段落の前半で検索する必要があります。

新しい end=mid-1=2 とfront=0 を変更しないままにして、新しい Mid=1 を設定します。このとき、x>midなので後半で探す必要があります。

新しいfront=mid+1=2とend=2を変更しないままにすると、新しいmid=2となり、この時点ではa[mid]=xとなり、検索は成功します。検索対象の数値が数列内の数値ではない場合、例えばx=25の場合、3回目の判定の際、x>a[mid]であるため、上記の規則に従い、front=mid+1とする。 、front=3、front>endと表示されます。 の場合、

は検索が失敗したことを意味します。

例: N 要素の順序付けられた

配列 内でユーザーが入力したデータ x を検索します。アルゴリズムは次のとおりです:

1. 検索範囲front=0、end=N-1を決定し、中間項mid=(front+end)/2を計算します。

2. a[mid]=x またはfront>=endの場合は検索を終了し、そうでない場合は下方向に進みます。

3. if a[mid] x は、検索される要素の値が中央の要素よりも小さい範囲内にあることを意味します。 Mid-1 から end までを計算し、mid を再計算し、実行ステップ 2 に進みます。

アルゴリズム複雑度分析

時間計算量

1.最後の要素（または最初の要素）のワーストケース探索 マスター定理 T(n)=T(n/2)+O(1) so T(n)=O(logn)

2. 中央の要素 O(1) を見つける最良のケースは、中央の要素 (奇数長のシーケンスの中央、偶数長のシーケンスの中央) を見つけることです。左の要素へ)

空間複雑度:

S(n)=n

package com.bjpowernode.test;
public class BinarySearch {
  // 查找次数
  static int count;
  /**
   * @param args
   */
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    System.out.println(searchRecursive(array, 0, array.length - 1, 9));
    System.out.println(count);
    count = 0;
    System.out.println(searchLoop(array, 9));
    System.out.println(count);
  }
  /**
   * 执行递归二分查找，返回第一次出现该值的位置
   *
   * @param array
   *      已排序的数组
   * @param start
   *      开始位置
   * @param end
   *      结束位置
   * @param findValue
   *      需要找的值
   * @return 值在数组中的位置，从0开始。找不到返回-1
   */
  public static int searchRecursive(int[] array, int start, int end,
      int findValue) {
    // 如果数组为空，直接返回-1，即查找失败
    if (array == null) {
      return -1;
    }
    count++;
    if (start <= end) {
      // 中间位置
      int middle = (start + end) / 1;
      // 中值
      int middleValue = array[middle];
      if (findValue == middleValue) {
        // 等于中值直接返回
        return middle;
      } else if (findValue < middleValue) {
        // 小于中值时在中值前面找
        return searchRecursive(array, start, middle - 1, findValue);
      } else {
        // 大于中值在中值后面找
        return searchRecursive(array, middle + 1, end, findValue);
      }
    } else {
      // 返回-1，即查找失败
      return -1;
    }
  }
  /**
   * 循环二分查找，返回第一次出现该值的位置
   *
   * @param array
   *      已排序的数组
   * @param findValue
   *      需要找的值
   * @return 值在数组中的位置，从0开始。找不到返回-1
   */
  public static int searchLoop(int[] array, int findValue) {
    // 如果数组为空，直接返回-1，即查找失败
    if (array == null) {
      return -1;
    }
    // 起始位置
    int start = 0;
    // 结束位置
    int end = array.length - 1;
    while (start <= end) {
      count++;
      // 中间位置
      int middle = (start + end) / 2;
      // 中值
      int middleValue = array[middle];
      if (findValue == middleValue) {
        // 等于中值直接返回
        return middle;
      } else if (findValue < middleValue) {
        // 小于中值时在中值前面找
        end = middle - 1;
      } else {
        // 大于中值在中值后面找
        start = middle + 1;
      }
    }
    // 返回-1，即查找失败
    return -1;
  }
}

以上が二分検索を実装するための Java コード例の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。