Java uses binary search method to implement sorting number index function example explanation

This article mainly introduces Java's use of the divide-and-conquer algorithm to implement the sorting index function, and analyzes the related operating techniques of the java divide-and-conquer algorithm for sorting indexing based on specific examples. Friends in need can refer to the following

The example in this article describes Java's use of the divide-and-conquer algorithm to implement the sorting index function. Share it with everyone for your reference, the details are as follows:

/**
 * 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);
  }
}

The above is the detailed content of Java uses binary search method to implement sorting number index function example explanation. For more information, please follow other related articles on the PHP Chinese website!