Maison >Java >javaDidacticiel >Java utilise une méthode de recherche binaire pour implémenter l'explication de l'exemple de fonction d'index de numéro de tri

Java utilise une méthode de recherche binaire pour implémenter l'explication de l'exemple de fonction d'index de numéro de tri

巴扎黑
巴扎黑original
2017-09-19 11:39:341364parcourir

Cet article présente principalement l'utilisation par Java de l'algorithme diviser pour régner pour implémenter la fonction d'index de tri. Il analyse les techniques de fonctionnement associées de l'algorithme java diviser pour régner pour trier l'indexation sur la base d'exemples spécifiques. peut s'y référer

L'exemple de cet article décrit l'utilisation par Java de l'algorithme diviser pour régner pour implémenter la fonction d'index de tri. Partagez-le avec tout le monde pour votre référence, les détails sont les suivants :


/**
 * Find the first q and return the index
 * First method is brutal force
 * Second may
 * be pid and Conquer
 *
 * @author open201
 *
 */
public class Ono {
  /**
   * f(n) = s.length = n;
   *
   * @param s
   * @param q
   * @return
   */
  public static int BrutalForceSearch(int[] s, int q) {
    for (int i = 0; i < s.length; i++) {
      if (q == s[i])
        return i;
    }
    return -1;
  }
  /**
   * f(n) = log(n)
   *
   * @param s
   * @param q
   * @return
   */
  public static int DCSearch(int[] s, int q, int startIndex, int endIndex) {
    if (startIndex > endIndex)
      return -1;
    else {
      int mid = (startIndex + endIndex) / 2;
      if (s[mid] == q)
        return mid;
      else {
        if (s[mid] > q)
          return DCSearch(s, q, startIndex,mid-1);
        else
          return DCSearch(s, q, mid+ 1,endIndex);
      }
    }
  }
  public static void main(String[] args) {
    int [] s = new int[10000000];
    for(int i = 0;i<10000000;i++){
      s[i] = i;
    }
    int q = 10000000-1;
    long startTime = System.currentTimeMillis();
    System.out.println(BrutalForceSearch(s, q));
    long endTime = System.currentTimeMillis();
    System.out.println(endTime-startTime);
    startTime = System.currentTimeMillis();
    System.out.println(DCSearch(s, q, 0, s.length - 1));
    endTime = System.currentTimeMillis();
    System.out.println(endTime-startTime);
  }
}

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!

Déclaration:
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn