Exemple de code Java pour implémenter la recherche binaire

Cet article présente principalement les informations pertinentes sur la recherche binaire Java. Les amis qui en ont besoin peuvent se référer à l'

Algorithme

Si vous avoir Le nombre de groupes est 3, 12, 24, 36, 55, 68, 75, 88. Pour vérifier la valeur donnée 24. Vous pouvez définir trois variables avant, milieu, fin pour pointer respectivement vers les limites supérieure, moyenne et inférieure des données, mid=(front+end)/2. 　　

Commencez par front=0 (pointant vers 3), end=7 (pointant vers 88 ), puis mid=3 (pointant vers 36) ). Parce que mid>x, il doit être recherché dans la première moitié du paragraphe.

Laissez les nouveaux end=mid-1=2 et front=0 rester inchangés, puis le nouveau mid=1. A ce moment, x>mid, il faut donc le rechercher dans la seconde moitié.

Laissez les nouveaux front=mid+1=2 et end=2 rester inchangés, puis le nouveau mid=2, à ce moment a[mid]=x, la recherche est réussie. Si le nombre à rechercher n'est pas un nombre dans la séquence, par exemple x=25, lorsque le troisième jugement est effectué, x>a[mid], selon les règles ci-dessus, soit front=mid+1, c'est-à-dire , front=3, front>end apparaît Dans le cas de

, cela signifie que la recherche a échoué.

Exemple : Rechercher les données x saisies par l'utilisateur dans un tableau ordonné avec N éléments. L'algorithme est le suivant :

1. Déterminez la plage de recherche front=0, end=N-1 et calculez le terme médian mid=(front+end)/2.

2. Si a[mid]=x ou front>=end, terminez la recherche sinon, continuez vers le bas.

3. Si a[mid]06a320d07b2a84b37281b9bed006f2d6x, cela signifie que la valeur de l'élément à trouver ne peut être que dans une plage plus petite que l'élément du milieu, puis attribuez la valeur de mid-1 à la fin. , et recalculez le milieu, passez à l'étape 2.

Analyse de la complexité des algorithmes

Complexité temporelle

1. Pire situation Trouvez le dernier élément (ou premier élément) Théorème de Master T(n)=T(n/2)+O(1) donc T(n)=O(logn)

2. Meilleur Dans le cas de trouver le élément du milieu O(1), l'élément recherché est l'élément du milieu (l'élément du milieu du tableau de longueur impaire, l'élément du milieu gauche du tableau de longueur paire)

Complexité spatiale :

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;
  }
}

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!