本帖最后由 淡忘初学者 于 2015-8-25 17:39 编辑
以下内容基于张孝祥老师视频课程笔记:
数组数据的查找也是数组操作中不可或缺的一个部分,但数组的查找操作,不同的代码在java中运行的情况也不一样,接下来以一般查找和折半查找为例,进行数组查找操作的回顾: - public class ArrayDemo2 {
- public static void main(String[] args) {
- //定义一个数组
- int[] arr=new int[]{12,31,53,11,7,101};
- //使用自定义的一般查找方法:
- search(arr,28);
- //使用自定义的折半查找方法并输出:
- System.out.println("利用折半查找所找元素的下标为:"+halfsearch(arr,53));
- //使用自定义的第二种折半查找方式:
- System.out.println("利用第二种折半查找方式所查找元素的下标为:"+halfsearch_0(arr,12));
- }
- /*
- * 数组的查找操作:给出一个数,在数组中找到相应数并明确其位置。
- * 对数组进行遍历,找到相同数并告知其角标,数则找出。
- */
- public static void search(int[] arr,int key)
- {
- int a=0;
- for (int x=0;x<arr.length ;x++ )
- {
- if (arr[x]==key)
- { if (a>0)
- System.out.print("和"+x);
- else
- System.out.print("所要查找的数角标为:"+x);
- a++;
- }
- }
- if (a==0)
- System.out.print("所要查找的数不存在");
- System.out.println();
- }
- /*折半查找:查找的数组中数据必须是顺序的,先从中间数查起,与所找数比较大小:
- * 如果中间数比所找数大,则再将中间数上 一位和第一位数之间数再折半查找;
- * 反之,如果中间数比所找数小,则将中间数下一位与最后一位数再折半查找;
- * 优点:提高了效率,但是必须要保证该数组是有序的数组。
- */
- public static int halfsearch(int[] arr,int key)
- {
- int min=0,max=arr.length-1,mid;
- mid=(min+max)/2;//先找出中间角标
- while (arr[mid]!=key)
- {
- if (arr[mid]>key)//如果中间角标对应的元素比所要查找数大,则所查找数在0至mid-1之间角标对应数之间
- max=mid-1;
- else if (arr[mid]<key)//如果中间角标对应的元素比所要查找数小,则所查找数在mid+1至max之间角标对应数之间
- min=mid+1;
- mid=(min+max)/2;//再继续折半
- if (min>max)//min>max时,说明查找数不在数组之列
- return -1;
- }
- return mid;
- }
- /*
- * 折半查找的第二种方式:
- */
- public static int halfsearch_0(int[] arr1,int key)
- {
- int min=0,max=arr1.length-1,mid;
- while (min<=max)//现将min<=max作为循环条件
- {
- mid=(min+max)/2;//再依次做出如上之判断
- if (key>arr1[mid])
- min=mid+1;
- else if (key<arr1[mid])
- max=mid-1;
- else
- return mid;
- }
- return -1;//不满足循环条件,则输出为-1(查找数不在数组之列)
- }
- }
复制代码 运行结果:
后面我会发每章节回顾的程序,如果你们觉得有可看性的话就继续关注吧~~谢谢各位了。
|