黑马程序员技术交流社区

标题: 代码练习题之数组的基本查找和高级二分查找 [打印本页]
作者: huang_bing_hua    时间: 2016-2-28 15:23
标题: 代码练习题之数组的基本查找和高级二分查找
  1. package cn.itcast_04;

  3. /*
  4. * 二分法查找给定的有序数组中特定元素所在索引
  5. * 分析步骤：
  6. *                 A:定义一个有序的数组
  7. *                 B:定义最大索引，定义最小索引
  8. *                 C:计算出中间索引
  9. *                 D:拿中间索引值与value比较
  10. *                         如果不同
  11. *                                 大了 在左边找
  12. *                                 小了 在右边找
  13. *                         如果相同 返回中间索引值
  14. *                 E:重新计算索引
  15. *                                 大了 max = mid -1 （因为比过的我们就不用再看了）
  16. *                                 小了 min = mid +1
  17. *                 F:回到第三步
  18. * 注意：(给定的数组如果有序，用二分查找；
  19. *                 如果无序，用基本查找，因为如果你先排序的话，你就是人为的改变了原始数组的元素索引值)
  20. */

  22. public class ArrayDemo {
  23.         public static void main(String[] args) {
  24.                 int[] arr = { 13, 56, 67, 89, 90 };
  25.                 int index = getIndex(arr, 67);
  26.                 System.out.println("有序数组中67这个元素的索引值是:"+ index);
  27.                 int[] arr1 = {67,56,13,90,89};
  28.                 int index2 = getIndex2(arr1,67);
  29.                 System.out.println("无序数组中67这个元素的索引值是:"+ index2);

  31.         }

  33.         public static int getIndex2(int[] arr, int value) {
  34.                 //针对所要查找的元素不存在，我先假设不存在，给返回值定为-1
  35.                 int index =-1;
  36.                 for (int x=0;x<arr.length;x++) {
  37.                         if (arr[x] == value) {
  38.                                 //一旦存在改变索引，并退出遍历
  39.                                 index = x;
  40.                                 break;
  41.                         }
  42.                 }
  43.                 return index;
  44.         }

  46.         public static int getIndex(int[] arr, int value) {
  47.                 int min = 0;
  48.                 int max = arr.length - 1;
  49.                 int mid = (min + max) / 2;
  50.                 while (arr[mid] != value) {
  51.                         if (arr[mid] > value) {
  52.                                 max = mid - 1;
  53.                         } else {
  54.                                 min = mid + 1;
  55.                         }
  56.                         //针对所要查找的元素不存在
  57.                         if (min > max) {
  58.                                 return -1;
  59.                         }
  60.                         mid = (min + max)/2;
  61.                 }
  62.                 return mid;

  64.         }
  65. }
复制代码






欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2