java 13-1 数组高级二分查找

时间:2022-09-26 22:53:20

  查找:
    1、基本查找:数组元素无序(从头找到尾)
    2、二分查找(折半查找):数组元素有序 pS:数组的元素必须有顺序,从小到大或者从大到小。以下的分析是从小到大的数组
  二分查找分析:
    A:先对数组进行对半(也就是设置 min索引为0,max索引为arr.length-1,然后对半的 索引mid为(min+max)/2)
    B:把所需要查找的数据x跟arr[mid]进行对比
       a:两者的值相等,就返回mid索引
       b:两者不等:
          1、如果 x > arr[mid],则 min索引的值改变为:min = mid+1,然后 mid 要重新赋值 :(min+max)/2
          2、如果 x < arr[mid],则 max索引的值改变为:max = mid-1,然后 mid 要重新赋值 :(min+max)/2
    C:重复B的动作
    D:注意:为了避免查找一个不存在的数据时,会出现死循环,所以要在B中加入一个限制条件:
       if(min > max){
          return -1;
          }
    E:以上定义为方法:
       a:返回类型:int(因为要的是所查找数据的索引)
       b:参数列表:int[] arr(所查找的数组)和 int x(x是所要查找的数据)

 import java.util.Scanner;
public class ArrayDemo1{ public static void main(String[] args) {
//定义一个数组
int[] arr = {12,31,34,45,56,78,80,87};
//创建键盘输入
Scanner sc = new Scanner(System.in);
System.out.println("请输入想要查找的数据:");
int x = sc.nextInt(); //调用方法
int index = choose(arr,x);
System.out.println("你所查找的数据的索引是:"+index);
} //定义二分查找的方法
public static int choose(int[] arr,int x){ //定义min,max,mid索引的值
int min = 0;
int max = arr.length -1;
int mid = (min + max)/2; //把所需要查找的数据x跟arr[mid]进行对比
//两者不等:
while( x != arr[mid]){
//1、如果 x > arr[mid]
if( x > arr[mid]){
min = mid + 1;
}
//2、如果 x < arr[mid]
else if( x < arr[mid]){
max = mid - 1;
}
//加入判断,防止死循环
if( min > max){
return -1;
}
//不管上面哪种情况,mid都要进行重新赋值的
mid = (min + max )/2;
}
//如果 x = arr[mid],就返回mid
return mid;
} }

2、 二分查找法的注意事项:
    注意:下面这种做法是有问题的。
       因为数组本身是无序的,所以这种情况下的查找不能使用二分查找。
       虽然先排序了,但是排序的时候已经改变了最原始的元素索引。
       所以以后遇到无序数组,进行查找的话,还是用基本查找的方法

 public class ArrayDemo2 {
public static void main(String[] args) {
// 定义数组
int[] arr = { 24, 69, 80, 57, 13 }; // 先排序
bubbleSort(arr);
// 后查找
int index = getIndex(arr, 80);
System.out.println("index:" + index);
} // 冒泡排序代码
public static void bubbleSort(int[] arr) {
for (int x = 0; x < arr.length - 1; x++) {
for (int y = 0; y < arr.length - 1 - x; y++) {
if (arr[y] > arr[y + 1]) {
int temp = arr[y];
arr[y] = arr[y + 1];
arr[y + 1] = temp;
}
}
}
} // 二分查找
public static int getIndex(int[] arr, int value) {
// 定义最大索引,最小索引
int max = arr.length - 1;
int min = 0; // 计算出中间索引
int mid = (max + min) / 2; // 拿中间索引的值和要查找的值进行比较
while (arr[mid] != value) {
if (arr[mid] > value) {
max = mid - 1;
} else if (arr[mid] < value) {
min = mid + 1;
} // 加入判断
if (min > max) {
return -1;
} mid = (max + min) / 2;
} return mid;
}
}

java 13-1 数组高级二分查找的更多相关文章

  1. Java实现递增数组的二分查找

    package com.algorithm; import java.util.ArrayList;import java.util.List; /** * 类功能描述: * * @author Ba ...

  2. Java数据结构和算法总结-数组、二分查找

    前言:在平时开发中数组几乎是最基本也是最常用的数据类型,相比链表.二叉树等又简单很多,所以在学习数据和算法时用数组来作为一个起点再合适不过了.本篇博文的所有代码已上传 github ,对应工程的 ar ...

  3. Java数组之二分查找

    简单的二分查找 package com.kangkang.array; public class demo03 { public static void main(String[] args) { / ...

  4. &lbrack;算法&rsqb;&lbrack;LeetCode&rsqb;Search a 2D Matrix——二维数组的二分查找

    题目要求 Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the ...

  5. &lbrack;19&sol;03&sol;13-星期三&rsqb; 数组&lowbar;二维数组&amp&semi;冒泡排序&amp&semi;二分查找

    一.二维数组 多维数组可以看成以数组为元素的数组.可以有二维.三维.甚至更多维数组,但是实际开发中用的非常少.最多到二维数组(我们一般使用容器代替,二维数组用的都很少). [代码示例] import ...

  6. PHP-----二维数组和二分查找

    二维数组由行和列组成.由arr[$i][$j]表示,先后表示行和列,类似于坐标点. 打印二维数组-----通过两次遍历,第一次遍历每一行,第二次遍历每一行的具体元素,并且通过使用count($arr[ ...

  7. &lbrack;c&sol;c&plus;&plus;&rsqb; programming之路(15)、多维数组和二分查找法&comma;小外挂

    一.多维数组 #include<stdio.h> #include<stdlib.h> void main(){ ][]; int i,j; ; i < ; i++) { ...

  8. java学习之—递归实现二分查找法

    /** * 递归实现二分查找法 * Create by Administrator * 2018/6/21 0021 * 上午 11:25 **/ class OrdArray{ private lo ...

  9. 【大视野入门OJ】1083:数组的二分查找

    Description 在1500个整数中查整数x的位置,这些数已经从小到大排序了.若存在则输出其位置,若不存在则输出-1. Input 第一行,一个整数x 后面1500行,每行一个整数 Output ...

随机推荐

  1. display&colon;none与visible&colon;hidden的区别

    display:none和visible:hidden都能把网页上某个元素隐藏起来,但两者有区别: display:none ---不为被隐藏的对象保留其物理空间,即该对象在页面上彻底消失,通俗来说就 ...

  2. 我们的html

    http://files.cnblogs.com/files/eeroom/mac-Bootstrap.rar http://files.cnblogs.com/files/eeroom/CSharp ...

  3. git 笔记1

    代码 kamil@ubuntu:~/github/xzdz$ git init Initialized empty Git repository in /home/kamil/github/xzdz/ ...

  4. C语言范例学习03-下

    树与图 3.5 二叉树及其应用 PS:二叉树是最经典的树形结构,适合计算机处理,具有存储方便和操作灵活等特点,而且任何树都可以转换成二叉树. 实例101 二叉树的递归创建 实例102 二叉树的遍历 问 ...

  5. 从SQL2008R2导入数据到SQL2005

    从SQL2008R2导入数据到SQL2005,数据很大,数据文件大概有120G. 尝试过直接离线附加,失败 尝试过备份还原,失败 最后找到了 1.先执行 exec sp_msforeachtable ...

  6. FACE&plus;&plus;学习二、获得face属性

    http://blog.csdn.net/lyq8479/article/details/17362685 为了防止网页丢失还是自己保存一份安全一点 人脸检测API介绍 在Face++网站的“API文 ...

  7. &lbrack;置顶&rsqb;&NewLine; xamarin Tablayout&plus;Viewpager&plus;Fragment顶部导航栏

    最近几天不忙,所以把项目中的顶部导航栏的实现归集一下.android中使用TabLayout+ViewPager+Fragment制作顶部导航非常常见,代码实现也比较简单.当然我这个导航栏是基于xam ...

  8. shell sed过滤器详解

    1. Sed简介sed 是一种在线编辑器,它一次处理一行内容.处理时,把当前处理的行存储在临时缓冲区中,称为"模式空间"(pattern space),接着用sed命令处理缓冲区中 ...

  9. day038 navicat pymysql

    今日内容: 1.navicat 2.pymysql 1.navicat 需要掌握 #1. 测试+链接数据库 #2. 新建库 #3. 新建表,新增字段+类型+约束 #4. 设计表:外键 #5. 新建查询 ...

  10. docker 开发常用命令总结

    Docker 常用命令总结,镜像下载,到docker容器创建,常用docker命令的 增删查 1.镜像下载,从hub.docker.com中下载最新版本的postgres docker pull po ...