黑马程序员技术交流社区

标题: 第04天-07-数组 [打印本页]
作者: 周志伟    时间: 2013-4-11 05:28
标题: 第04天-07-数组
本帖最后由 周志伟 于 2013-4-11 21:21 编辑
  1. class  ArrayTest4
  2. {
  3.     public static void main(String[] args)
  4.    {
  5.          int[] arr = {1,3,2,8,9,10};
  6.                 int index = getIndex(arr,3);
  7.                 System.out.println("index="+index);
  8.    ｝

  10.         //定义功能，获取key第一次出现在数组中的位置。如果返回是-1，那么代表该key在数组中不存在。     
  11.       public static int getIndex(int[] arr,int key)
  12.      {
  13.          for(int x=0; x<arr.length; x++)
  14.          {
  15.             if(arr[x]==key)
  16.                 return x;
  17.          }
  18.          return -1;//负数表示没有被找到，没有这个角标
  19.      }
  20. ｝

  22. 输出结果：1。
复制代码

7027fee34b9d2e6f4220c&690.jpeg (83.12 KB, 下载次数: 9)

7027fee34b9d2e6f4220c&690.jpeg
作者: 胡滨    时间: 2013-4-11 07:13
  1. public class BinarySearch
  2. {

  4.         public static int binarySearch(int[] srcArray, int des)

  6.         {

  8.                 int low = 0;

  10.                 int high = srcArray.length - 1;

  12.                 while (low <= high)
  13.                 {

  15.                         int middle = (low + high) / 2;

  17.                         if (des == srcArray[middle])
  18.                         {

  20.                                 return middle;

  22.                         }
  23.                         else if (des < srcArray[middle])
  24.                         {

  26.                                 high = middle - 1;

  28.                         }
  29.                         else
  30.                         {

  32.                                 low = middle + 1;

  34.                         }

  36.                 }

  38.                 return -1;

  40.         }

  42.         public static void main(String[] args)

  44.         {

  46.                 int[] src = new int[] { 1, 3, 5, 7, 8, 9 };

  48.                 System.out.println(binarySearch(src, 3));

  50.         }

  52. }
复制代码
传给cpu，让cpu做电位运算{:soso_e142:}
作者: 陈雨    时间: 2013-4-11 09:10
你写的代码不是折半查找，你是将数组内的元素遍历与key一一比较，看是否和key相同。
用折半查找如楼上的代码，这种方法的特点是已经数组排好序了的，思想和高等数学里的二分法相似。它是将Key和数组中间的数字mid对比，如果key比mid小，说明key在min与mid之间，所以另一半数组mid与max之间的数就不用找了，同理key比mid大也是一样的。当key比mid小时，这是就让key与min与mid中间的数比较大小，如此反复，但是max的角标会变化，下次max的值就取mid角标-1的数。一直不断缩小范围，取到min的角标大于max为止，返回-1就是这个原因，因为min>max说明已经全面取完了，要么key在这个数组内，就找到了，返回-1说明不存在
作者: 小菜凉碟    时间: 2013-4-11 09:28
楼主，这不是折半查找，折半查找是针对有序数组有的如{1，3，5，7，9},数组元素是从大到小排列或从小到大，以下是折半查找代码，希望能帮到你
  1. public static int getIndex(int[] arr,int key){
  2. int min = 0;
  3. int max = arr.length - 1;
  4. int mid = (min+max)/2;

  6. //如果中间不等于我们要找的数,就通过循环进行不断的查找
  7. while(arr[mid] != key){
  8. if(key > arr[mid]){
  9. min = mid + 1;//如果要找的数比中间值大,那么小角标值改变
  10. }
  11. else if(key < arr[mid]){
  12. max = mid - 1;//如果要找的数比中间值小,那么大角标值改变
  13. }

  15. //如果没有怎么办？min max
  16. if(min>max) {//如果min>max证明已经没有可以折半的可能性了,说明要找的数不在这个数组
  17. return -1;
  18. }

  20. mid = (min+max)/2;
  21. }
  22. return mid;
  23. }
复制代码
作者: 黄玉昆    时间: 2013-4-11 19:49
如果问题未解决，请继续追问，如果没有问题了，请将帖子分类 改为“已解决”，谢谢
作者: 周志伟    时间: 2013-4-11 21:13
胡滨 发表于 2013-4-11 07:13
传给cpu，让cpu做电位运算

奥，知道了，arr[0]和key是在ＣＰＵ中进行比较，原来如此。谢谢啦
作者: 周志伟    时间: 2013-4-11 21:14
陈雨 发表于 2013-4-11 09:10
你写的代码不是折半查找，你是将数组内的元素遍历与key一一比较，看是否和key相同。
用折半查找如楼上的代 ...

:)谢谢啦。
作者: 周志伟    时间: 2013-4-11 21:14
小菜凉碟 发表于 2013-4-11 09:28
楼主，这不是折半查找，折半查找是针对有序数组有的如{1，3，5，7，9},数组元素是从大到小排列或从小到大， ...

非常感谢
作者: 蓝色骨头    时间: 2013-4-11 21:26
堆和栈都是内存
cpu在做运算的时候只要知道地址就可以了
比较的时候可以将它们加载到寄存器做一下减法运算，看结果是否为0，或者其他的实现方式
作者: 周志伟    时间: 2013-4-11 21:31
蓝色骨头 发表于 2013-4-11 21:26
堆和栈都是内存
cpu在做运算的时候只要知道地址就可以了
比较的时候可以将它们加载到寄存器做一下减法运算 ...

奥奥，晓得了，谢谢啦



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