精华内容
下载资源
问答
  • import java.util.Scanner; class Test_数组 { public static void main(String[] args) { int[] arry = new int[]{-11,90,87,3,6,23,398}; //静态赋值:定义一个数组 bianLi(arry);//遍历整个数组 调用了...
    import java.util.Scanner;
    class Test_数组 {
        public static void main(String[] args) {
            int[] arry = new int[]{-11,90,87,3,6,23,398}; //静态赋值:定义一个数组
            bianLi(arry);//遍历整个数组 调用了bianLi这个方法
            int max = getMax(arry); //调用方法得到数组最大值
            int min = getMin(arry); //调用方法得到数组最小值
            System.out.println();
            System.out.println("最大元素是:"+max+"  最小元素是:"+min);//打印数组最大值,最小值
            Scanner sc = new Scanner(System.in); //定义一个Scanner的对象
            System.out.println("Input a number");//输入要查询的数字
            int num = sc.nextInt();//接收键盘输入的数字
            int index = getIndex(arry,num);// 调用getIndex方法得到查询数字的索引
            System.out.println(num+"的索引是"+index);//打印出查找数字的索引,-1代表没有这个数字
            arryReverseAll(arry);//反转整个数组
            bianLi(arry);//打印反转后的数组
        }
    
            /*数组的遍历*/
        public static void bianLi(int[] arr){
            for (int i = 0;i < arr.length ;i++ ){
                System.out.print(arr[i]+"  ");
            }
        }
    
            /*数组最大值*/
        public static int getMax(int[] arr){
            int max = arr[0];
            for (int i = 1;i < arr.length ;i++ ){
                if (arr[i] > max){
                    max = arr[i];
                }
            }
            return max;
        }
            
    
            /*数组最小值*/
        public static int getMin(int[] arr){
            int min = arr[0];
            for (int i = 1;i < arr.length ;i++ ){
                if (arr[i] < min){
                    min = arr[i];
                }
            }
            return min;
        }
            
        
            /* 查找数组中的元素,返回值的索引*/
        public static int getIndex(int[] arry,int value){
            for (int i = 0;i < arry.length ;i++ ){
                if (arry[i] == value){
                    return i;
                }
            }
            return -1;
        }
        /*交换两个数的值*/
        public static void arryReverse(int[] arry,int index1,int index2){
            int temp = arry[index1];
            arry[index1] = arry[index2];
            arry[index2] = temp;
        }
        /*反转整个一维数组*/
        public static void arryReverseAll(int[] arry){
            for (int start = 0,end = arry.length - 1;start < end;start++,end--){
                arryReverse(arry,start,end);
            }
        }
    }

    运行结果:

     

    转载于:https://www.cnblogs.com/xiuzidbk/p/9307208.html

    展开全文
  • 根据上图所示:假设有一个数组,数组里面的元素有F[k]-1个,这个数组被分成了三份:F[k-1]-1,1和F[k-2]-1这三份(mid点是一个元素,长度为1)。 根据斐波那契数列的公式: F[k]=F[k-1]+ F[k-2]...

    斐波那契查找算法:前提是一个有序数组。
    斐波那契数列:1,1,2,3,5,8,13,21。。。。。。
    主要思想:通过斐波那契数列找到数组黄金分割点附近的下标,即mid。
    在这里插入图片描述
    根据上图所示:假设有一个数组,数组里面的元素有F[k]-1个,这个数组被分成了三份:F[k-1]-1,1和F[k-2]-1这三份(mid点是一个元素,长度为1)。
    根据斐波那契数列的公式:
    F[k]=F[k-1]+ F[k-2],将这个公式变型为F[k]-1=F[k-1]-1+ F[k-2]-1+1。
    根据斐波那契查找法,mid的选择方法为mid = low+F[k-1]-1,使mid位于黄金分割点附近。
    在这里插入图片描述
    例如上图所示:low=0,F[k-1]-1=4,mid= 4。所以k=4时:4=0+5-1。
    当数组的元素为{1,2,3,4,5,6}时,为了满足斐波那契数列,数组的长度需要满足:
    While(array.Length > F[k]-1){
    K++;
    }
    K=0开始每次加1,直到F[k]-1的值大于或等于数组的长度为止。
    因此,根据这个条件,上面的数组长度为6,在k=5时,F[5] – 1=7,数组需要正价长度及元素,将数组长度变为7,在后面赋值数据最后一个元素的值。

    ```package SearchTest;
    
    import java.util.Arrays;
    
    public class FibonacciSearchTest {
    	public static int max = 20;// 定义斐波那契数列的长度
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		int[] arr = { 1, 8, 10, 89, 100, 123, 200 };
    		System.out.println(FibonacciSearch(arr, 123));
    	}
    
    	// 实现一个斐波那契数列的方法
    	// 1,1,2,3,5,8,13,21,34,55......
    	public static int[] Fibonacci() {
    		int[] F = new int[max];
    		F[0] = 1;
    		F[1] = 1;
    		for (int i = 2; i < max; i++) {
    			F[i] = F[i - 1] + F[i - 2];
    		}
    		return F;
    	}
    
    	// 实现斐波那契查找的步骤
    	public static int FibonacciSearch(int[] arr, int findVal) {
    		int low = 0;// 数据的左边下标
    		int high = arr.length - 1;// 数组的右边下标
    		int[] f = Fibonacci();// 将斐波那契数列传递给f数组
    		int k = 0;// 用来弥补F[k]-1余arr.Length的差距
    		int mid = 0;// 黄金分割点
    		// 判断数组的长度是否小于F[k]-1,如果小于就用k计数
    		// 这个地方是数组长度与斐波那契数列中的数据进行比较
    		// 因此,数组的长度是arr.Length,
    		while (arr.length > f[k] - 1) {// f[5] = 8,high = 5;
    			k++;// 直到找到一个k的值,可以使f[k]-1大于high时结束,k为斐波那契数列下标
    		}
    		// 这时需要填充数组arr,需要达到斐波那契数列的长度
    		// 但是arr得长度已经固定了,因此需要一个临时的数组
    		int[] tmp = Arrays.copyOf(arr, f[k] - 1);//
    		for (int i = high + 1; i < tmp.length; i++) {
    			tmp[i] = arr[high];
    		}
    		// 开始循环
    		while (low <= high) {
    			mid = low + f[k - 1] - 1;// 黄金分割点
    			if (findVal < tmp[mid]) {
    				high = mid - 1;
    				// 这个k=k-1可以理解为现在对新的数组进行查找,也是斐波那契数列,此时的数据长度为F[k-1]-1
    				// 现在可以令k-1=K,这样这个数组的长度可以写成F[K]-1,mid = low+F[K-1]-1即low+F[k-2]-1
    				k = k - 1;//
    			} else if (findVal > tmp[mid]) {
    				low = mid + 1;
    				// 这个k=k-2可以理解为现在对新的数组进行查找,也是斐波那契数列,此时的数据长度为F[k-2]-1
    				// 现在可以令k-2=K,这样这个数组的长度可以写成F[K]-1,mid = low+F[K-1]-1即low+F[k-3]-1
    				k = k - 2;
    			} else {// 由于数组后面的数据都是最后一个元素填充的,mid可能是那些填充数据的下标,因此需要比较与真实数组长度的大小
    				if (mid <= high) {
    					return mid;
    				} else {
    					return high;
    				}
    			}
    		}
    		return -1;
    	}
    }
    
    
    
    展开全文
  • 要实现查找指定数值在元素有序的数组中存储的位置(索引),返回该位置(索引)(索引就是下标)。1. 我们使用数组最中间位置的元素值与要查找的指定数值进行比较,若相等,返回中间元素值的索引2. 最中间位置的...

    要实现查找指定数值在元素有序的数组中存储的位置(索引),返回该位置(索引)(索引就是下标)。

    1.     我们使用数组最中间位置的元素值与要查找的指定数值进行比较,若相等,返回中间元素值的索引

    2.     最中间位置的元素值与要查找的指定数值进行比较,若不相等,则根据比较的结果,缩小查询范围为上次数组查询范围的一半;

    再根据新的查询范围,更新最中间元素位置,然后使用中间元素值与要查找的指定数值进行比较

    n 比较结果相等,返回中间元素值的索引

    n 比较结果不相等,继续缩小查询范围为上次数组查询范围的一半,更新最中间元素位置,继续比较,依次类推。

    3.  当查询范围缩小到小于0个元素时,则指定数值没有查询到,返回索引值-1。

    解题步骤:

    1.     定义3个用来记录索引值的变量,变量min记录当前范围最小索引值,初始值为0;变量max记录当前范围最大索引值,初始值为数组长度-1;变量mid记录当前当前范围最中间元素的索引值,初始值为(min+max)/ 2

    2.     使用循环,判断当前范围下,最中间元素值与指定查找的数值是否相等

    n 若相等,结束循环,返回当前范围最中间元素的索引值mid

    n 若不相等,根据比较结果,缩小查询范围为上一次查询范围的一般

    u 中间元素值 比 要查询的数值大,说明要查询的数值在当前范围的最小索引位置与中间索引位置之间,此时,更新查询范围为:

    范围最大索引值 = 上一次中间索引位置 -1;

    u 中间元素值 比 要查询的数值小,说明要查询的数值在当前范围的最大索引位置与中间索引位置之间,此时,更新查询范围为:

    范围最小索引值 = 上一次中间索引位置 +1;

    u 在新的查询范围中,更新中间元素值的位置,再次使用最中间元素值与指定查找的数值是否相等。

                     中间索引值 = (范围最小索引值 +范围最大索引值) / 2;

    3.  每次查询范围缩小一半后,使用if语句判断,查询范围是否小于0个元素,若小于0个元素,则说明指定数值没有查询到,返回索引值-1。

       

    代码如下:

    //二分查找法(折半查找法)

    publicstaticint halfSearch(int[] arr,intnumber) {

        //定义3个变量,用来记录min, min, mid的位置

        intmin = 0;

        intmax = arr.length-1;

        intmid = 0;

            while (min <=max) {

               mid =(min+max)/2;

            //没找了, 更新范围,继续比较

            //更新范围

            if (arr[mid] > number) {

                //在左边

                max = mid-1;

            } elseif(arr[i]< number){

                //在右边

                min = mid+1;

            }

            else{

                  returnmid;

              }

         

        return-1;

    }

    展开全文
  • java递归实现二分查找

    2020-04-15 12:39:51
    然后就是思路:首先取数组中间元素与要查找元素进行比较,根据结果做下一步的操作:相等,返回对应下标;中间元素小,则在数组后半段内重复操作;中间元素小,在数组前半段内重复操作。这样不断操作,最后就可以...

    思路

    二分查找大家肯定都很清楚了吧,如果不清楚,可以看这里 二分查找 。然后就是思路:首先取数组中间元素与要查找的元素进行比较,根据结果做下一步的操作:相等,返回对应下标;中间元素小,则在数组后半段内重复操作;中间元素小,在数组前半段内重复操作。这样不断操作,最后就可以得到结果。
    注意:给定数组应该是排好序的。我这里使用的是升序数组,如果降序数组,则上述操作应该反过来

    代码

    public class BinarySearch {
    	//递归实现二分查找
    	public static void Sort(int a[], int key, int start, int end) {//key为要查找的值
    		if(start < end) {			//防止越界溢出
    			int mid = (start + end)/2;	//获取中间元素
    			if (key == a[mid]) {	//相等返回下标
    				System.out.println("下标为"+mid);
    			}else if (key > a[mid]){	//数组元素小,对后半段进行操作
    				Sort(a, key, mid + 1, end);
    			}else {	//数组元素大,对前半段进行操作
    				Sort(a, key, start, mid - 1);
    			}
    		}
    	}
    	public static void main(String[] args) {
    		int a[] = {1,2,3,4,5,6,7,8,9};	//该数组必须为升序数组
    		int start = 0;	//起始位置
    		int end = a.length;	//末尾,但是注意此时end的值
    		Sort(a, 6, start, end);
    	}
    }
    
    展开全文
  • 可以根据字面意思理解二分查找的核心思想就是把数组分区,首先定义一个左指针left(数组第一个元素下标)和一个右指针right(数组末元素下表),之后计算数组中间位置的指针mid(mid=left+(right-left)/2)进行分区,第...
  • 数组的遍历 获取最大值最小值 数组的反转 数组的查找 练习 定义方法创建指定大小的数组,并添加指定元素 拼接两个数组 感觉数组的运用还是得靠大量的实操练习才能深刻理解,像遍历取大小值和反转查下标这种系统本身...
  • java数据结构之ArrayList

    2019-03-14 13:21:43
    java数据结构之ArrayList ArrayList 优点: 1、根据下标遍历元素效率较高。 2、根据下标访问元素效率较高。...3、在数组的基础上封装了对元素操作的方法。...2、根据内容查找元素的效率较低。 ArrayList的底...
  • 数组中根据输入数据大小输出存放下标的位置5.数组中元素指定位置往后覆盖6.数组中在指定位置插入指定值总结 一、什么数组? 示例:数组是用来存放相同类型的数据的集合 二、储存空间(栈空间和堆空间) 三、代码...
  • 本节内容:1:数组查表法(根据键盘录入索引,查找对应星期)(掌握)2:重载指定元素第一次在数组中出现的索引(掌握)3:本节总结&下节预告本文出处:《凯哥陪你学系列之java基础篇.Java基本语法篇》》中第29篇 数组8...
  • 查找(Searching)就是根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素(或记录)。 (一)顺序表查找:从表的第一个记录开始依次往后,直到最后一个记录,查找到的话返回,否则返回-1。 // 线性...
  • java的ArrayList源码解读

    2020-03-03 14:34:56
    谈到ArrayList,先说说优缺点: 因为ArrayList底层使用数组实现,所以优缺点与数组类似。 优点: ...2、根据内容查找元素的效率较低。 扩容规则:每次扩容现有容量的50%。 1. 先看看ArrayL...
  • java容器

    2018-09-03 20:50:00
    hashmap 哈希表也叫散列表,是一种非常...在数组 中根据下标查找某个元素,一次定位就可以达到,哈希表利用了这种特性,哈希表的主干就是数组。 hashMap有数组+链表组成的,数组是HashMap的主题。 转载于:http...
  • 动态数组java简单实现

    2021-03-13 11:20:13
    动态数组java简单实现 ...1、指定下标查找 2、指定元素查找(返回结果) 改: 1、指定下标修改 2、指定元素修改(返回结果) 合并: 1、去重合并 2、直接合并 扩容 : 新建数组 拷贝原数组 修改引用 ...
  • Java基础语法 说说集合框架的简单...//根据下标查询元素 public static int queryElementByIndex(int[] arr, int index) { return arr[index]; } //根据元素查找下标 public static int queryIndexByElement(int[]
  • Java HashMap底层实现

    2018-10-26 21:26:43
    在数组中根据下标查找某个元素,一次定位就可以达到,哈希表利用了这种特性, 哈希表 的主干就是数组。哈希表的事件复杂度为O(1),在不考虑冲突的情况下, 可以非常快速找到。 存储位置 = f(关键字) HashMa....
  • java 数组

    2018-04-08 15:44:36
    原本认为数组一种简单的数据结构,但是看到后来才发现,很多的数据结构最终的实现都是由数组实现的。数组的局限性分析: ①... ②、查找慢,当然如果根据下标查找是很快的。但是通常我们都是根据元素值来查找,...
  • 概念: 数组是Java数据结构中最基本的...根据元素值查找慢:如果根据下标查找会比较快,但是根据元素值查找对于无序数组需要从第一个元素开始遍历进行查找知道查找到所需要的数据。如果是有序数组可以通过合适的排序...
  • Java中HashMap的理解

    2020-03-26 20:20:40
    利用的前提:数组中根据下标访问元素的时间复杂度是O(1) 查找过程: 在一个Key-Set中查找指定Key的过程。 因为Key-Set中的key太多了,所以查找会变慢。 如果Key-Set中的Key较少,无论什么查找算法都比较快。 Hash...
  • JavaJava 集合--list

    2018-01-19 19:39:32
    list List 接口 List接口是一个有序的 Collection,使用此接口能够精确的控制每个元素插入的位置,能够通过索引 (元素在List中位置,类似于数组的下标)来访问List中的元素,第一个元素的索引为 0...查找元素效率...
  • java 数据结构

    2018-06-20 22:20:44
    比如我们最常用的数组,就是一种数据结构,有独特的承载数据的方式,按顺序排列,其特点就是你可以根据下标快速查找元素,但是因为在数组中插入和删除元素会有其它元素较大幅度的便宜,所以会带来较多的消耗,所以...
  • Java8 HashMap

    2019-11-20 15:34:24
    Java7 HashMap查找的时候,根据 hash 值我们能够快速定位到数组的具体下标,但是之后的话,需要顺着链表一个个比较下去才能找到我们需要的,时间复杂度取决于链表的长度,为 O(n)O(n)O(n)。 为了降低这部分的开销,...
  • Java的二分搜索法

    2018-12-08 18:50:26
    import java.util.Arrays; public class Demo2 { /* * 二分搜索法(折半... * 注意:二份搜索法:根据元素查找下标 * 找到返回当前元素下标,没有找到返回负数 */ public static void myBinarySearch(int[]...
  • Java集合学习总结

    2021-01-20 16:10:23
    ArrayList:底层数据结构是数组(动态数组),查询快(因为底层是数组,可以根据下标快速查找),增删慢,线程不安全,效率高,可以存储重复元素 什么是动态数组?我们知道,在Java中数组一旦初始化,那么长度就...
  • 根据下标查找是O(1); 插入和删除是O(n) 适用于读多写少的场景 1.2.链表 链表(linked list) 是一种在物理上非连续、 非顺序的数据结构, 由若干节点(node) 所组成。分单链表和双链表,一般实现的时候会使用head/...
  • Java后端面试常常会碰见这道题,...对于随机访问,ArrayList优于LinkedList,ArrayList可以根据下标元素进行随机访问,而LinkedList的每一个元素都依靠地址指针和它后一个元素连接到一起,在这种情况下,查找某个...
  • Java集合-List源码

    2019-09-21 16:29:30
    可以根据下标获取和查找指定元素;List允许插入重复元素,允许插入多个null元素。 List继承自Collection的接口,List也是集合的一种。List是有序队列,List中的每一个元素都会有一个索引,第一个元素的索引是0,往后...
  • 无序、无下标元素不可重复(即无重复)(三无)HashSet(存储结构哈希表,先根据HashCode查找位置,如果当前位置没有元素,直接放置;如果有有元素,则执行equals,true则是重复的,false则形成链表。 数组+链表+...
  • java常用数据结构

    千次阅读 2015-03-11 22:32:15
    比如我们最常用的数组,就是一种数据结构,有独特的承载数据的方式,按顺序排列,其特点就是你可以根据下标快速查找元素,但是因为在数组中插入和删除元素会有其它元素较大幅度的移动,所以会带来较多的消耗,所以...
  • 一、数据结构数据结构由数据和结构两部分组成,就是将数据按照一定的结构组合起来,...二、数组数组表示一组有限个相同类型的数据的集合,顺序存储,下标从0开始,其特点是可以根据下标快速的查找元素,但在增加...

空空如也

空空如也

1 2 3 4 5 ... 7
收藏数 123
精华内容 49
关键字:

java根据下标查找元素

java 订阅