A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区
传智教育官网黑马程序员官网
只需一步,快速开始
小蜀哥哥
黑马粉丝团
黑马币:812
帖子:347
精华:0
© 小蜀哥哥 黑马粉丝团 / 2018-5-7 16:27 / 891 人查看 / 3 人回复 / 0 人收藏 转载请遵从CC协议 禁止商业使用本文
例如我们要完成以下需求: 要求在一个存储了多个整数的数组中查找指定元素所在的索引值示范代码如下: [Java] 纯文本查看 复制代码public class Test { public static void main(String[] args) { //准备好被查找的数组 int[] arr = { 2, 3, 5, 1, 6, 4, 9, 7, 8 }; //调用查找方法查找给定数组中5元素所在的索引值,并接收查找到的索引 int index = getIndex(arr, 5); //输出索引 System.out.println("index:"+index); } public static int getIndex(int[] arr, int num) { for (int i = 0; i < arr.length; i++) { //按顺序遍历获取数组中的每个元素和要查找的元素进行比较 if (num == arr[i]) { //如果要查找的元素值等于对应位置的元素值,则返回索引 return i; } } //如果所有的元素都不等于要查找的元素,则返回-1表示没有找到 return -1; } }控制台输出:index:2
public class Test { public static void main(String[] args) { //准备好被查找的数组 int[] arr = { 2, 3, 5, 1, 6, 4, 9, 7, 8 }; //调用查找方法查找给定数组中5元素所在的索引值,并接收查找到的索引 int index = getIndex(arr, 5); //输出索引 System.out.println("index:"+index); } public static int getIndex(int[] arr, int num) { for (int i = 0; i < arr.length; i++) { //按顺序遍历获取数组中的每个元素和要查找的元素进行比较 if (num == arr[i]) { //如果要查找的元素值等于对应位置的元素值,则返回索引 return i; } } //如果所有的元素都不等于要查找的元素,则返回-1表示没有找到 return -1; } }
1 2 3 4 <font color='red'>5</font> 6 7 8 9 10 如果第一次猜的数字是5,并且能被告知5这个值是偏大还是偏小,就能排除一半错误答案。<br/>为了能达到这个效果,那么这组数据必须是有序的
6 4 8 2 <font color='red'>3</font> 10 7 5 9 1假设要猜的数字是8,我们第一次猜了中间的数字3,但是如果数组不是有序的,就没法定位8到底在左半边还是右半边。
示范代码如下:
public class Test { public static void main(String[] args) { // 准备好一个有序的被查找数组 int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; // 调用查找方法查找给定数组中5元素所在的索引值,并接收查找到的索引 int index = getIndex(arr, 5); // 输出索引 System.out.println("index:" + index); } public static int getIndex(int[] arr, int num) { // 定义变量,表示查找数组范围的最左侧,先从0索引开始 int left = 0; // 定义变量,表示查找数组范围的最右侧,先从最大索引开始 int right = arr.length - 1; // 定义变量,表示查找范围的中间值 int mid; while (left <= right) { // 中间索引 = (左侧 + 右侧) / 2 // mid = (left + right) / 2; // 为了提高效率,我们可以用位运算代替除以运算 mid = (left + right) >>> 2 if (arr[mid] > num) { //如果中间元素大于要查找元素,则在中间元素的左侧去找正确元素,最右侧变为mid - 1 right = mid - 1; } else if (arr[mid] < num) { //如果中间元素小于要查找元素,则在中间元素的右侧去找正确元素,最左侧变为mid + 1 left = mid + 1; } else { // 如果不大不小,那么就正好是找到了,返回找到的索引 return mid; } } // 当查找范围的最左侧和最右侧重叠后还没有找到元素,则返回-1表示没有找到 return -1; } }