java算法之二分查找法的实例详解

java算法之二分查找法的实例详解

原理

假定查找范围为一个有序数组（如升序排列），要从中查找某一元素，如果该元素在此数组中，则返回其索引，否则返回-1。通过数组长度可取出中间位置元素的索引，将其值与目标值比较，如果中间位置元素值大于目标值，则在左部分进行查找，如果中间位置值小于目标值，则在右部分进行查找，如此循环，直到结束。二分查找算法之所以快是因为它没有遍历数组的每个元素，而仅仅是查找部分元素就能找到目标或确定其不存在，当然前提是查找范围为有序数组。

Java的简单实现

package me.geed.algorithms; 

public class BinarySearch { 

  /**
   * 从一个有序数组(如升序)中找到值为key元素
   * @param key
   * @param array
   * @return 如果找到目标元素，则返回其在数组中的索引，否则返回-1
   */
  public static int find(int key, int[] array){
    int low = 0;
    int high = array.length - 1;
    while (low <= high) {
      int mid = low + (high - low) / 2;
      if (array[mid] > key) {
        high = mid - 1;
      } else if (array[mid] < key) {
        low = mid + 1;
      } else {
        return mid;
      }
    }
    return -1;
  } 

  public static void main(String[] args) {
    // TODO Auto-generated method stub
    int[] array = {2, 3, 5, 9, 10, 13, 23, 45, 78, 89, 100, 128, 256};
    System.out.println("目标元素索引值：" + BinarySearch.find(9, array));
    System.out.println("目标元素索引值：" + BinarySearch.find(26, array));
  } 

}

输出结果为：

目标元素索引值：3
目标元素索引值：-1

二分查找算法的时间复杂度

假设范围数组长度为N，则二分查找的时间复杂度为O（logN）

以上就是java算法中二分查找的实例详解，如有疑问请留言或到本站社区交流讨论，感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

赞 (0)

相关推荐

  • java数据结构之二分查找法 binarySearch的实例

    java数据结构之二分查找法 binarySearch的实例 折半查找法,前提是已经排好序的数组才可查找 实例代码: public class BinarySearch { int[] bArr; public void setArr(int[] bArr){ this.bArr=bArr; } public static void main(String[] args) { int arrLength=16; int[] bArr=new int[arrLength]; System.out.

  • 使用javascipt---实现二分查找法

    复制代码 代码如下: <html><head><meta http-equiv="Content-Type" content="text/html;charset=utf-8"><script type="text/javascript"> //window.alert(Math.floor(5.7)); //向下取整 输出5 //二分查找法 数组必须是有序的 function binarySeac

  • java算法之二分查找法的实例详解

    java算法之二分查找法的实例详解 原理 假定查找范围为一个有序数组(如升序排列),要从中查找某一元素,如果该元素在此数组中,则返回其索引,否则返回-1.通过数组长度可取出中间位置元素的索引,将其值与目标值比较,如果中间位置元素值大于目标值,则在左部分进行查找,如果中间位置值小于目标值,则在右部分进行查找,如此循环,直到结束.二分查找算法之所以快是因为它没有遍历数组的每个元素,而仅仅是查找部分元素就能找到目标或确定其不存在,当然前提是查找范围为有序数组. Java的简单实现 package me

  • python 二分查找和快速排序实例详解

    思想简单,细节颇多:本以为很简单的两个小程序,写起来发现bug频出,留此纪念. #usr/bin/env python def binary_search(lst,t): low=0 height=len(lst)-1 quicksort(lst,0,height) print lst while low<=height: mid = (low+height)/2 if lst[mid] == t: return lst[mid] elif lst[mid]>t: height=mid-1 e

  • C经典算法之二分查找法

    C经典算法之二分查找法 1.根据key查找所在数组的位置 #include <stdio.h> /* key = 9; 1 2 3 4 5 6 7 8 arr 3, 4, 5, 7, 9 , 11, 21, 23 low = 1 mid = (low + high)/2 = 4 high = 8; one arr[mid] = 7 < 9; so low = mid + 1 = 5; high = 8; mid = (low + high)/2 = 6 two arr[mid] = 11

  • js基本算法:冒泡排序,二分查找的简单实例

    知识扩充: 时间复杂度:算法的时间复杂度是一个函数,描述了算法的运行时间.时间复杂度越低,效率越高. 自我理解:一个算法,运行了几次时间复杂度就为多少,如运行了n次,则时间复杂度为O(n). 1.冒泡排序 解析:1.比较相邻的两个元素,如果前一个比后一个大,则交换位置. 2.第一轮的时候最后一个元素应该是最大的一个. 3.按照步骤一的方法进行相邻两个元素的比较,这个时候由于最后一个元素已经是最大的了,所以最后一个元素不用比较. function sort(elements){ for(var i

  • Java根据ip地址获取归属地实例详解

    Java根据ip地址获取归属地实例详解

    目录 引言 Java 中是如何获取 IP 属地的 首先需要写一个 IP 获取的工具类 内置的三种查询算法 使用方法 项目用到的全部依赖 引言 最近,各大平台都新增了评论区显示发言者ip归属地的功能,例如哔哩哔哩,微博,知乎等等. Java 中是如何获取 IP 属地的 主要分为以下几步 通过 HttpServletRequest 对象,获取用户的 IP 地址 通过 IP 地址,获取对应的省份.城市 首先需要写一个 IP 获取的工具类 因为每一次用户的 Request 请求,都会携带上请求的 IP 

  • Java使用AES加密和解密的实例详解

    Java使用AES加密和解密的实例详解 前言: AES的基本要求是,采用对称分组密码体制,密钥长度的最少支持为128.192.256,分组长度128位,算法应易于各种硬件和软件实现.1998年NIST开始AES第一轮分析.测试和征集,共产生了15个候选算法.1999年3月完成了第二轮AES2的分析.测试.2000年10月2日美国政府正式宣布选中比利时密码学家Joan Daemen 和 Vincent Rijmen 提出的一种密码算法RIJNDAEL 作为 AES. 在应用方面,尽管DES在安全上

  • Java设计模式之装饰模式原理与用法实例详解

    本文实例讲述了Java设计模式之装饰模式原理与用法.分享给大家供大家参考,具体如下: 装饰模式能在不必改变原类文件和使用继承的情况下,动态地扩展一个对象的功能.它是通过创建一个包装对象,也就是装饰来包裹真实的对象.JDK中IO的设计就用到了装饰模式,通过过滤流对节点流进行包装来实现功能的扩展. 装饰模式的角色的组成: ① 抽象构件(Component)角色:给出一个抽象接口,以规范准备接收附加工功能的对象.(InputStream.OutputStream) ② 具体构件(Concrete Co

  • FasfDFS整合Java实现文件上传下载功能实例详解

    FasfDFS整合Java实现文件上传下载功能实例详解

    在上篇文章给大家介绍了FastDFS安装和配置整合Nginx-1.13.3的方法,大家可以点击查看下. 今天使用Java代码实现文件的上传和下载.对此作者提供了Java API支持,下载fastdfs-client-java将源码添加到项目中.或者在Maven项目pom.xml文件中添加依赖 <dependency> <groupId>org.csource</groupId> <artifactId>fastdfs-client-java</arti

  • java 数据结构中栈和队列的实例详解

    java 数据结构中栈和队列的实例详解 栈和队列是两种重要的线性数据结构,都是在一个特定的范围的存储单元中的存储数据.与线性表相比,它们的插入和删除操作收到更多的约束和限定,又被称为限定性的线性表结构.栈是先进后出FILO,队列是先进先出FIFO,但是有的数据结构按照一定的条件排队数据的队列,这时候的队列属于特殊队列,不一定按照上面的原则. 实现栈:采用数组和链表两种方法来实现栈 链表方法: package com.cl.content01; /* * 使用链表来实现栈 */ public cl

随机推荐