精华内容
下载资源
问答
  • 二分查找算法JAVA

    2021-03-05 17:06:28
    1.二分查找又称折半查找,它是一种效率较高的查找方法。2.二分查找要求:(1)必须采用顺序存储结构 (2).必须按关键字大小有序排列3.原理:将数组分为三部分,依次是中值(所谓的中值就是数组中间位置的那个值)前,中值...

    1.二分查找又称折半查找,它是一种效率较高的查找方法。

    2.二分查找要求:(1)必须采用顺序存储结构 (2).必须按关键字大小有序排列

    3.原理:将数组分为三部分,依次是中值(所谓的中值就是数组中间位置的那个值)前,中值,中值后;将要查找的值和数组的中值进行比较,若小于中值则在中值前 面找,若大于中值则在中值后面找,等于中值时直接返回。然后依次是一个递归过程,将前半部分或者后半部分继续分解为三部分。

    4.实现:二分查找的实现用递归和循环两种方式

    5.代码:

    1 package other;

    2

    3 public class BinarySearch {

    4 /*

    5 * 循环实现二分查找算法arr 已排好序的数组x 需要查找的数-1 无法查到数据

    6 */

    7 public static int binarySearch(int[] arr, int x) {

    8 int low = 0;

    9 int high = arr.length-1;

    10 while(low <= high) {

    11 int middle = (low + high)/2;

    12 if(x == arr[middle]) {

    13 return middle;

    14 }else if(x

    15 high = middle - 1;

    16 }else {

    17 low = middle + 1;

    18 }

    19 }

    20 return -1;

    21 }

    22 //递归实现二分查找

    23 public static int binarySearch(int[] dataset,int data,int beginIndex,int endIndex){

    24 int midIndex = (beginIndex+endIndex)/2;

    25 if(data dataset[endIndex]||beginIndex>endIndex){

    26 return -1;

    27 }

    28 if(data

    29 return binarySearch(dataset,data,beginIndex,midIndex-1);

    30 }else if(data>dataset[midIndex]){

    31 return binarySearch(dataset,data,midIndex+1,endIndex);

    32 }else {

    33 return midIndex;

    34 }

    35 }

    36

    37 public static void main(String[] args) {

    38 int[] arr = { 6, 12, 33, 87, 90, 97, 108, 561 };

    39 System.out.println("循环查找:" + (binarySearch(arr, 87) + 1));

    40 System.out.println("递归查找"+binarySearch(arr,3,87,arr.length-1));

    41 }

    42 }

    展开全文
  • 二分查找也称折半查找(Binary Search),它的查找效率很好。二分查找有一个要求是必须采用顺序存储结构,而且表种的元素是有序的。只有满足这个条件我们才能使用二分查找。查找条件:查找区域的左边界,小于等于查找...

    二分查找也称折半查找(Binary Search),它的查找效率很好。二分查找有一个要求是必须采用顺序存储结构,而且表种的元素是有序的。只有满足这个条件我们才能使用二分查找。

    查找条件:

    查找区域的左边界,小于等于查找区域的右边界

    查找过程:

    1. 循环条件 == 查找条件

    2.计算序列中间下标位置

    3.如果待查找值value == 中间位置的元素的值 返回当前中间位置下标

    4.如果待查找值value   >   序列中间位置元素的值  左边界等于中间位置+1

    5.如果带查找值value   

    6.如果循环结束 返回 -1   (也就是没查找到,返回-1)

    源代码:

    import java.util.Scanner;

    /**

    * 二分查找 Demo

    *

    * @author zhipeng-Tong

    */

    public class BinarySearch {

    public static void main(String[] args) {

    // 已经排序好的数组

    int[] array = new int[]{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

    // 获取查找值

    Scanner sc = new Scanner(System.in);

    System.out.print("输入要查找值(0-9):");

    int findValue = sc.nextInt();

    // 查找

    int findIndexValue = searchIndexValue(array, findValue);

    System.out.println("查找值下标为:" + findIndexValue);

    }

    /**

    * 二分查找值元素

    *

    * @param array

    * 已排序的数组

    * @param findValue

    * 要查找的值

    * @return

    * 找到值时返回值的下标,没找到时返回-1

    */

    private static int searchIndexValue(int[] array, int findValue) {

    // 起始下标,和结束小标,声明中间值。

    int start = 0;

    int end = array.length - 1;

    int mid;

    // 查找区域的左边界,小于等于查找区域的右边界

    while (start <= end) {

    // 计算序列中间下标位置

    mid = (end + start) / 2;

    if (findValue == array[mid]) { // 如果待查找值value == 中间位置的元素的值, 返回当前中间位置下标

    return mid;

    } else if (findValue < array[mid]) { //如果带查找值value < 序列中间位置元素的值, 右边界等于中间位置-1

    end = mid - 1;

    } else { //如果待查找值value > 序列中间位置元素的值, 左边界等于中间位置+1

    start = mid + 1;

    }

    }

    return -1;

    }

    }

    展开全文
  • * 二分查找 */ public static final void testTwoPointSearch() { int[] source = new int[] { 1,13,21,35,39,51,62,78,99 }; System.out.println(twoPointSearch(source, 22)); System.o
    package Test;
    
    public class Test8 {
    
        /**
         * 二分查找
         */
        public static final void testTwoPointSearch() {
    
            int[] source = new int[] { 1,13,21,35,39,51,62,78,99 };
    
    
            System.out.println(twoPointSearch(source, 22));
            System.out.println(twoPointSearch(source, 21));
            System.out.println(twoPointSearch(source, 1));
            System.out.println(twoPointSearch(source, 99));
    
            System.out.println(twoPointSearchByRecursion(source, 22, 0, source.length-1));
            System.out.println(twoPointSearchByRecursion(source, 21, 0, source.length-1));
            System.out.println(twoPointSearchByRecursion(source, 1, 0, source.length-1));
            System.out.println(twoPointSearchByRecursion(source, 99, 0, source.length-1));
    
        }
    
    
        /**
         *
         * @param source
         * @param search
         * @return 返回匹配的下标
         */
        public static final int twoPointSearch(int[] source, int search) {
            int min = 0;
            int max = source.length - 1;
            int mid = ( max - min  ) >> 1 ;
    
            while (mid >= 0 && mid <= max && max >= min) {
                if(source[mid] == search ) {
                    return mid;
                }
    
                if(source[mid] > search ) { // 在souce前半部分查找
                    max = mid - 1;
                } else {                     // 在souce后半部分查找
                    min = mid + 1;
                }
    
                mid = ((max-min) >> 1) + min ;
            }
    
            return -1;
        }
    
        /**
         * 二分查找,递归版本
         * @param source   有序数组
         * @param search   待查询元素
         * @param min      开始下标
         * @param max      结束下标(初始值为有序数组长度减1)
         * @return
         */
        public static final int twoPointSearchByRecursion(int[] source, int search, int min, int max) {
            int mid = ((max-min) >> 1) + min ;
    
            if(mid >= 0 && mid <= max && max >= min ) {
                if(source[mid] == search ) {
                    return mid; //返回下标
                }
    
                if(source[mid] > search ) { // 在souce前半部分查找
                    max = mid - 1;
                } else {                     // 在souce后半部分查找
                    min = mid + 1;
                }
    
                return twoPointSearchByRecursion(source, search, min, max) ;
    
            } //否则结束递归
    
            return -1;
        }
    }
    
    
    展开全文
  • 数组中的查找算法和二分查找算法-Java语言实现 前言 以前大二的时候,为了激发学妹们对编程的兴趣,我决定给她们分享一些编程的技能。由于之前给学弟分享过解一元二次方程-Java语言实现,所以要是这次还是给学妹们...

    数组中的查找算法和二分查找算法-Java语言实现

    前言

    以前大二的时候,为了激发学妹们对编程的兴趣,我决定给她们分享一些编程的技能。由于之前给学弟分享过解一元二次方程-Java语言实现,所以要是这次还是给学妹们分享一样的知识,大概会显得我很low吧,我也会因此失去她们的宠幸。

    我一直苦苦思索,该给她们分享什么好呢……

    突然有个长得很乖的学妹跟我说,想找男朋友。于是我计上心头,干脆我给她们写一个查找算法吧,但是只写一个查找算法怕是无法满足学妹们对知识的渴望,她们对知识的如狼似虎般的心,我是深有体会的……

    学妹露出邪魅的一笑对我说,她想快点找到男朋友

    我一听就明白了,果然女孩子做什么事都喜欢快一点亦或是更快一点

    她这句话给我了灵感,直接查找太慢,我再优化一下,整个二分查找算法不是更快了吗?这样肯定能满足她们了吧

    说干就干,于是我便理清思路开始写代码

    正文

    我跟学妹们解释,在大学里找到合适的男朋友就像是从数组中查找到你要找的数一样

    首先,创建一个能存储10个元素的int型数组

    int array[]=new int[]{3,6,7,9,10,1,2,4,5,8};
    

    然后输入要查询的数字,再跟数组里的元素进行比较

    		int i;
            for (i = 0; i <array.length ; i++) {
                int k=i+1;
                if(key==array[i]) {
                    System.out.println("找到了,是第" + k + "个数");
                    break;
                }
            }
            if(i==array.length)
                System.out.println("没找到");
    

    如果迭代变量i已经超出了数组的长度,那么输出没找到

    下面是完整的代码

    public class search {
        public static void main(String[] args) {
            int array[]=new int[]{3,6,7,9,10,1,2,4,5,8};
    
            System.out.println("请输入你要查找的数: ");
    
            Scanner sc=new Scanner(System.in);
    
            int key=sc.nextInt();
    
            int i;
            for (i = 0; i <array.length ; i++) {
                int k=i+1;
                if(key==array[i]) {
                    System.out.println("找到了,是第" + k + "个数");
                    break;
                }
            }
            if(i==array.length)
                System.out.println("没找到");
        }
    }
    

    二分搜索算法

    上面写的最最最垃圾的搜索算法,无脑+暴力

    下面我们来写有技术含量的折半查找

    这次我们需要创建的是一个按照升序排列的数组

    int array[]=new int[]{1,2,3,4,5,6,7,8,9,10};
    

    然后定义几个变量

    		int key;//key是要查找的数
     		int low=0;//low是数组的第一个元素的下标
            int high=array.length-1;//high是数组最后一个元素的下标
            int middle;//middle是数组中间的元素的下标
    

    现在正式开始查找

     while(high>=low) {
    
               middle=(low+high)/2;
    
                if(array[middle]<key){
                    low=middle+1;
                }
                else if (array[middle]>key){
                    high=middle-1;
                }
    
                else {
                    System.out.println("你要查找的数在第"+(middle+1)+"个");
                    break;
                }
            }
           if(low > high)
               System.out.println("找不到");
    

    如果查找的数是6,那么如下面的图所示
    请添加图片描述
    折半查找,就是不停的对半查找,直到找到为止

    要是low的值大于了high的值,说明这整个数组已经遍历完了,但是还是没有找到我们要查找的数,所以只能输出找不到

    完整代码如下:

    public class search2 {
        public static void main(String[] args) {
            int array[]=new int[]{1,2,3,4,5,6,7,8,9,10};
    
            System.out.println("请输入你要查找的数: ");
    
            Scanner scanner = new Scanner(System.in);
    
            int key=scanner.nextInt();
    
            int low=0;
            int high=array.length-1;
            int middle;
    
           while(high>=low) {
    
               middle=(low+high)/2;
    
                if(array[middle]<key){
                    low=middle+1;
                }
                else if (array[middle]>key){
                    high=middle-1;
                }
    
                else {
                    System.out.println("你要查找的数在第"+(middle+1)+"个");
                    break;
                }
            }
           if(low > high)
               System.out.println("找不到");
        }
    }
    
    

    总结

    我们能很清楚的知道,暴力查找算法的时间复杂度是O(n)

    而折半查找算法的时间复杂度为O( l o g 2 n {log_2{n}} log2n

    所以当数组中的元素越多时,折半查找所展示出来的算法优越性就越好

    后续

    于是我终于满足了学妹们,她们对折半查找非常满意,毕竟这能让她们更快的找到男朋友

    然后,结果是……

    在这里插入图片描述
    终究是错付了,学妹又被辜负了,我为什么要说又?

    今天的分享就到这里,我们下期见~

    本文章选自微信公众号onceCode
    如果大家喜欢喜欢的话欢迎关注公众号
    附上微信公众号链接
    在这里插入图片描述

    展开全文
  • 这篇文章主要介绍了Java二分查找算法实现代码实例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下二分查找:两种方式:非递归方式和递归方式主要思路:对于已排序...
  • 二分法查找,也称为折半法,是一种在有序数组中查找特定元素的搜索算法、实现思路: (1)首先,从数组的中间元素开始搜索,如果该元素正好是目标元素,则搜索过程结束,否则执行下一步。 (2)如果目标元素...
  • 一、概述有序数组中常常用到二分查找,能提高查找的速度。今天,我们用顺序查找和二分查找实现数组的增删改查。二、有序数组的优缺点优点:查找速度比无序数组快多了缺点:插入时要按排序方式把后面的数据进行移动三...
  • 二分查找又称折半查找,它是一种效率较高的查找方法。折半查找的算法思想是将数列按有序化(递增或递减)排列,查找过程中采用跳跃式方式查找,即先以有序数列的中点位置为比较对象,如果要找的元素值小 于该中点元素...
  • 二分查找算法java实现) 二分查找 又叫折半查找,是一种简单又快速的查找算法 适用于(有序列表) ​ 每次都通过跟区间的中间元素对比,将待查找的区间缩小为之前的一半,直到找到要查找的元素,或者区间被缩小为0...
  • java算法|二分查找

    2021-03-15 17:08:19
    0x01,二分查找概念二分查找又称为折半查找,它是一种效率较高的查找方法,但是,折半查找要求线程表必须采用顺序存储结构,且表中的元素是有序的。0x02,先进行数据元素的排序折半查找的前提是有序,无论升序还是...
  • 二分查找算法是在有序数组中用到的较为频繁的一种算法。在未接触二分查找算法时,最通用的一种做法是,对数组进行遍历,跟每个元素进行比较,其时间复杂度为O(n),但二分查找算法则更优,因为其查找时间复杂度为O...
  • Java实现二分查找算法

    2021-02-27 18:47:37
    二分查找:两种方式: 非递归方式和递归方式主要思路: 对于已排序的数组(先假定是从小到大排序), 先定义两个"指针", 一个"指向"首元素low, 一个"指向"末尾元素high.然后, 开始折半比较, 即让要查找的数与数组中间的...
  • //二分查找测试类//注意:二分查找必须用在有序列表中进行二分查找public class BinaryChopTest {public static void main(String[] args) {int[] arrays = {1, 6, 10, 11, 12, 100};for (int i = 0; i <= 10; i+...
  • 最近在努力的复习一些基本的算法,本期就以java二分查找算法进行详细的概述(之前面试的时候,手写算法被坑过,一把泪啊)。进入正题吧~ 一、二分查找算法的介绍 二分查找,又名折半查找。顾名思义,一半一半去...
  • 二分查找是一种查询效率非常高的查找算法。又称折半查找。一、算法思想有序的序列,每次都是以序列的中间位置的数来与待查找的关键字进行比较,每次缩小一半的查找范围,直到匹配成功。一个情景:将表中间位置记录的...
  • //对于一个有序数组,我们通常采用二分查找的方式来定位某一元素,请编写二分查找算法,在数组中查找指定元素。public class test03 {public static void main(String[] args) {int A[] = { 4, 4, 5, 5, 5, 5 };...
  • 基础算法:冒泡排序冒泡排序:将无序的数据有序化,将相邻的两个元素进行比较, 使最大值或者最小值一步步冒上去,所以称为冒泡排序.冒泡排序思想:以升序为例:在一个数组中,将相邻的两个元素A与B进行比较,如果A大于B 则A...
  • Java实现折半查找(二分查找)的递归和非递归算法转 : http://wintys.blog.51cto.com/425414/94051/***名称:BinarySearch*功能:实现了折半查找(二分查找)的递归和非递归算法.*说明:* 1、要求所查找的数组已有序,...
  • 请对一个有序数组{1,3,7,8,9,10}进行二分查找,输入一个整数,看看该数是否在数组中,在则返回该数下标 二、二分查找思路分析 1.首先确定该数组中间的下标(left+right)/2:(左端点加右端点的和除以2),记...
  • 面试真题详解:排序矩阵中的从小到大第k个数在一个排序矩阵中找从小到大的第 k 个整数。排序矩阵的定义为:每一行递增,每一列也...文章九章算法NineChapter2020-11-25115浏览量Java 查找算法这个问题有几个点要先...
  • 1、前提:二分查找的前提是需要查找的数组必须是已排序的,我们这里的实现默认为升序2、原理:将数组分为三部分,依次是中值(所谓的中值就是数组中间位置的那个值)前,中值,中值后;将要查找的值和数组的中值进行...
  • java二分查找算法

    2021-02-28 12:18:04
    算法:当数据量很大适宜采用该方法。采用二分法查找时,数据需是有序不重复的。 基本思想:假设数据是按升序排序的,对于给定值 x,从序列的中间位置开始比较,如果当前位置值等于 x,则查找成功;若 x 小于当前位置...
  • 二分查找算法

    2021-08-10 09:08:42
    二分查找属于递归查找的一种,其主要思想是将一个有序数组,分为二分,进行递归,反复为之。 注意: 二分查找法只适用于从有序的数列中进行查找(比如数字和字母等),将数列排序后再进行查找 二分查找法的运行时间为...
  • 1、算法思想:二分查找又称折半查找,它是一种效率较高的查找方法。时间复杂度:O(nlogn)二分算法步骤描述:① 首先在有序序列中确定整个查找区间的中间位置 mid = (low+ high )/ 2② 用待查关键字值与中间位置的...
  • java算法之二分查找法的实例详解原理假定查找范围为一个有序数组(如升序排列),要从中查找某一元素,如果该元素在此数组中,则...二分查找算法之所以快是因为它没有遍历数组的每个元素,而仅仅是查找部分元素就能...
  • 二分查找法作为一种常见的查找方法,将原本是线性时间提升到了对数时间范围,大大缩短了搜索时间,但它有一个前提,就是必须在有序数据中进行查找。 二分查找很好写,却很难写对,据统计只有10%的程序员可以写出没有...
  • 问: 给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。 例: 输入: nums = [-1,0,3,5,9,12], target = 9 ...
  • 二分查找过程二分查找,也称折半查找,是对有序序列的查找算法,时间复杂度为O(log n).本文的重点是某元素二分查找的比较次数。特别要注意的是查找的上下边界问题(下面有解释)例:22 34 55 77 89 93 99 102 120 140...
  • 二分查找算法(非递归)介绍 二分查找法只适用于从有序的数列中进行查找(比如数字和字母等),将数列排序后再进行查找 二分查找法的运行时间为对数时间O(㏒₂n) ,即查找到需要的目标位置最多只需要㏒₂n步,假设从[0,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 111,898
精华内容 44,759
关键字:

二分查找算法java

java 订阅