A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

本帖最后由 L.I.F.E 于 2013-5-17 21:01 编辑

练习:有一个有序的数组,想要将一个元素插入到该数组中,还要保证该数组是有序的。如何获取该元素在数组中的位置。

疑问是:定义数组为int[] arr = {0,1,2,3,4,5,6,7,8,9},如果要插入的值为10,那么通过折半查找函数确定的插入位置是9而不是10?。

6 个回复

倒序浏览
eycrckag 来自手机 中级黑马 2013-5-17 19:30:23
沙发
不要返回-1改成返回min。min的值就是你要插入的角标位置!
回复 使用道具 举报
eycrckag 来自手机 中级黑马 2013-5-17 19:32:26
藤椅
如果你的数组里已经有10,你返回min就是返回的是10的角标,把你的新10放进去。数组里面的10往后顺延
回复 使用道具 举报
eycrckag 发表于 2013-5-17 19:32
如果你的数组里已经有10,你返回min就是返回的是10的角标,把你的新10放进去。数组里面的10往后顺延 ...

把10放进去,应该是挤走了9的位置了!
回复 使用道具 举报
看看min是不是定义错了
回复 使用道具 举报
返回角标值应该是10的,楼主贴出代码look下
回复 使用道具 举报
  1. class ArrayTest
  2. {
  3.         public static void main(String[] args)
  4.         {
  5.                 int[] arr = {0,1,2,3,4,5,6,7,8,9};
  6.                 int index = getIndex(arr,11);
  7.                 System.out.println("index="+index);
  8.                 printArray(arr);
  9.         }

  10.         public static void printArray(int []arr)
  11.         {
  12.                 for (int x=0;x<arr.length ;x++ )
  13.                 {
  14.                         System.out.print(arr[x]+", ");
  15.                 }
  16.        
  17.         }
  18.         public static int getIndex(int[] arr,int key)
  19.         {
  20.                 int min = 0,max = arr.length-1,mid;

  21.                 while(min<=max)
  22.                 {
  23.                         mid = (max+min)/2;

  24.                         if(key>arr[mid])
  25.                                 min = mid + 1;
  26.                         else if(key<arr[mid])
  27.                                 max = mid - 1;
  28.                         else
  29.                                 return mid;
  30.                 }
  31.                 return min;
  32.         }
  33. }
复制代码
我还准备把数值插入再打印 但是发现我不会。。。囧
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马