欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Java使用分治算法实现排序数索引功能示例【二分搜索】

程序员文章站 2024-02-28 15:10:04
本文实例讲述了java使用分治算法实现排序数索引功能。分享给大家供大家参考,具体如下: /** * find the first q and return t...

本文实例讲述了java使用分治算法实现排序数索引功能。分享给大家供大家参考,具体如下:

/**
 * find the first q and return the index
 * first method is brutal force
 * second may
 * be divid 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);
  }
}

更多关于java算法相关内容感兴趣的读者可查看本站专题:《java数据结构与算法教程》、《java操作dom节点技巧总结》、《java文件与目录操作技巧汇总》和《java缓存操作技巧汇总

希望本文所述对大家java程序设计有所帮助。