查找:
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 数组高级二分查找的更多相关文章
-
Java实现递增数组的二分查找
package com.algorithm; import java.util.ArrayList;import java.util.List; /** * 类功能描述: * * @author Ba ...
-
Java数据结构和算法总结-数组、二分查找
前言:在平时开发中数组几乎是最基本也是最常用的数据类型,相比链表.二叉树等又简单很多,所以在学习数据和算法时用数组来作为一个起点再合适不过了.本篇博文的所有代码已上传 github ,对应工程的 ar ...
-
Java数组之二分查找
简单的二分查找 package com.kangkang.array; public class demo03 { public static void main(String[] args) { / ...
-
[算法][LeetCode]Search a 2D Matrix——二维数组的二分查找
题目要求 Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the ...
-
[19/03/13-星期三] 数组_二维数组&;冒泡排序&;二分查找
一.二维数组 多维数组可以看成以数组为元素的数组.可以有二维.三维.甚至更多维数组,但是实际开发中用的非常少.最多到二维数组(我们一般使用容器代替,二维数组用的都很少). [代码示例] import ...
-
PHP-----二维数组和二分查找
二维数组由行和列组成.由arr[$i][$j]表示,先后表示行和列,类似于坐标点. 打印二维数组-----通过两次遍历,第一次遍历每一行,第二次遍历每一行的具体元素,并且通过使用count($arr[ ...
-
[c/c++] programming之路(15)、多维数组和二分查找法,小外挂
一.多维数组 #include<stdio.h> #include<stdlib.h> void main(){ ][]; int i,j; ; i < ; i++) { ...
-
java学习之—递归实现二分查找法
/** * 递归实现二分查找法 * Create by Administrator * 2018/6/21 0021 * 上午 11:25 **/ class OrdArray{ private lo ...
-
【大视野入门OJ】1083:数组的二分查找
Description 在1500个整数中查整数x的位置,这些数已经从小到大排序了.若存在则输出其位置,若不存在则输出-1. Input 第一行,一个整数x 后面1500行,每行一个整数 Output ...
随机推荐
-
display:none与visible:hidden的区别
display:none和visible:hidden都能把网页上某个元素隐藏起来,但两者有区别: display:none ---不为被隐藏的对象保留其物理空间,即该对象在页面上彻底消失,通俗来说就 ...
-
我们的html
http://files.cnblogs.com/files/eeroom/mac-Bootstrap.rar http://files.cnblogs.com/files/eeroom/CSharp ...
-
git 笔记1
代码 kamil@ubuntu:~/github/xzdz$ git init Initialized empty Git repository in /home/kamil/github/xzdz/ ...
-
C语言范例学习03-下
树与图 3.5 二叉树及其应用 PS:二叉树是最经典的树形结构,适合计算机处理,具有存储方便和操作灵活等特点,而且任何树都可以转换成二叉树. 实例101 二叉树的递归创建 实例102 二叉树的遍历 问 ...
-
从SQL2008R2导入数据到SQL2005
从SQL2008R2导入数据到SQL2005,数据很大,数据文件大概有120G. 尝试过直接离线附加,失败 尝试过备份还原,失败 最后找到了 1.先执行 exec sp_msforeachtable ...
-
FACE++学习二、获得face属性
http://blog.csdn.net/lyq8479/article/details/17362685 为了防止网页丢失还是自己保存一份安全一点 人脸检测API介绍 在Face++网站的“API文 ...
-
[置顶]
 xamarin Tablayout+Viewpager+Fragment顶部导航栏
最近几天不忙,所以把项目中的顶部导航栏的实现归集一下.android中使用TabLayout+ViewPager+Fragment制作顶部导航非常常见,代码实现也比较简单.当然我这个导航栏是基于xam ...
-
shell sed过滤器详解
1. Sed简介sed 是一种在线编辑器,它一次处理一行内容.处理时,把当前处理的行存储在临时缓冲区中,称为"模式空间"(pattern space),接着用sed命令处理缓冲区中 ...
-
day038 navicat pymysql
今日内容: 1.navicat 2.pymysql 1.navicat 需要掌握 #1. 测试+链接数据库 #2. 新建库 #3. 新建表,新增字段+类型+约束 #4. 设计表:外键 #5. 新建查询 ...
-
docker 开发常用命令总结
Docker 常用命令总结,镜像下载,到docker容器创建,常用docker命令的 增删查 1.镜像下载,从hub.docker.com中下载最新版本的postgres docker pull po ...