Java分治法与二分搜索算法实例分析

 更新时间:2017年11月21日 10:24:35   作者:萌神哆啦A梦   我要评论
这篇文章主要介绍了Java分治法与二分搜索算法,简单讲述了分治法与二分搜索算法的原理并结合java实例分析了二分搜索算法的实现与使用技巧,需要的朋友可以参考下

本文实例讲述了Java分治法与二分搜索算法。分享给大家供大家参考,具体如下:

1、分治法

分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题,这些子问题相互独立且与原问题相同。递归的解这些子问题,然后将各子问题的解合并得到原问题的解。

分治法所能解决的问题一般具有以下几个特征:

  1) 该问题的规模缩小到一定的程度就可以容易地解决
  2) 该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质。
  3) 利用该问题分解出的子问题的解可以合并为该问题的解;
  4) 该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子子问题。

分治法的基本步骤:

分治法在每一层递归上都有三个步骤:

  分解:将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题;
  解决:若子问题规模较小而容易被解决则直接解,否则递归地解各个子问题;
  合并:将各个子问题的解合并为原问题的解。

它的一般的算法设计模式如下:

Divide-and-Conquer(P)
if |P|≤n0
then return(ADHOC(P))
//将P分解为较小的子问题 P1 ,P2 ,...,Pk
for i←1 to k
do yi ← Divide-and-Conquer(Pi) △ 递归解决Pi
T ← MERGE(y1,y2,...,yk) △ 合并子问题
return(T)

其中|P|表示问题P的规模;n0为一阈值,表示当问题P的规模不超过n0时,问题已容易直接解出,不必再继续分解。ADHOC(P)是该分治法中的基本子算法,用于直接解小规模的问题P。因此,当P的规模不超过n0时直接用算法ADHOC(P)求解。算法MERGE(y1,y2,...,yk)是该分治法中的合并子算法,用于将P的子问题P1,P2 ,...,Pk的相应的解y1,y2,...,yk合并为P的解。

子问题的划分:人们从大量实践中发现,在用分治法设计算法时,最好使子问题的规模大致相同。换句话说,将一个问题分成大小相等的k个子问题的处理方法是行之有效的。许多问题可以取 k = 2。这种使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想,它几乎总是比子问题规模不等的做法要好。

2、二分搜索

大部分程序员应该都知道二分搜索的大致原理,这里不再赘述。需要说明的是二分搜索是所有以比较为基础的搜索算法时间复杂度最低的算法。用二叉树描速二分查找算法,最坏情况下与二叉树的最高阶相同。比较二叉树线性查找也可用二叉树表示,最坏情况下比较次数为数组元素数量。任何一种以比较为基础的搜索算法,其最坏情况所用时间不可能低于O(logn)。

二分搜索程序清单如下:

import java.util.Scanner;
public class BinarySearch {
  public static int BinarySearch (int[] a,int x,int n) {
    int left = 0;
    int right = n - 1;
    while(left <= right) {
      int middle = (left + right) / 2;
      if(x == a[middle]) return middle;
      if(x >= a[middle]) left = middle + 1;
      else right = middle - 1;
    }
    return -1;
  }
  public static void main(String args[]) {
    System.out.println("澳门金沙网上娱乐测试结果:");
    int[] a = new int[10];
    for(int i = 0; i < a.length; i++) {
      a[i] = i+1;
      System.out.print(a[i] + " ");
    }
    System.out.println();
    System.out.println("请输入你要查询的数:");
    Scanner sc = new Scanner(System.in);
    int b = sc.nextInt();
    int num = BinarySearch(a, b, a.length) + 1;
    System.out.println("要查找的数在第" + num + "个位置");
  }
}

运行结果:

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

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

相关文章

  • Spring注入方式有哪些

    Spring注入方式有哪些

    你知道Spring的注入方式有哪几种吗?这篇文章主要为大家详细介绍了Spring的注入方式,感兴趣的小伙伴们可以参考一下
    2016-09-09
  • java实现水波纹扩散效果

    java实现水波纹扩散效果

    这篇文章主要为大家详细介绍了java实现水波纹扩散效果,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
    2019-01-01
  • spring boot实现过滤器和拦截器demo

    spring boot实现过滤器和拦截器demo

    本篇文章主要介绍了spring boot实现过滤器和拦截器demo ,小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧
    2017-02-02
  • java中request常用方法小结

    java中request常用方法小结

    这篇文章主要介绍了java中request常用方法小结,需要的朋友可以参考下
    2014-10-10
  • java根据本地IP获取mac地址的方法

    java根据本地IP获取mac地址的方法

    这篇文章主要为大家详细介绍了java根据本地IP获取mac地址的方法,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
    2017-06-06
  • 用Java实现希尔排序的示例

    用Java实现希尔排序的示例

    问题:现有一段程序S,可以对任意n个数进行排序。如果现在需要对n^2个数进行排序,最少需要调用S多少次?只允许调用S,不可以做别的操作。我们用希尔排序来做解决这个
    2013-11-11
  • Spring Data JPA实现动态条件与范围查询实例代码

    Spring Data JPA实现动态条件与范围查询实例代码

    本篇文章主要介绍了Spring Data JPA实现动态条件与范围查询实例代码,非常具有实用价值,需要的朋友可以参考下
    2017-06-06
  • Java Resource路径整理总结

    Java Resource路径整理总结

    这篇文章主要介绍了 Java Resource路径整理总结的相关资料,需要的朋友可以参考下
    2017-03-03
  • 寻找二叉树最远的叶子结点(实例讲解)

    寻找二叉树最远的叶子结点(实例讲解)

    下面小编就为大家分享一篇寻找二叉树最远的叶子结点的实例讲解,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
    2017-12-12
  • java 多线程的同步几种方法

    java 多线程的同步几种方法

    这篇文章主要介绍了java 多线程的同步几种方法的相关资料,这里提供5种方法,需要的朋友可以参考下
    2017-09-09

最新评论