折半查找中元素插入数组中的问题，百思不得解，求助。。

黑妞~

本帖最后由 tacyjay在路上于 2014-3-21 19:31 编辑

/*
练习：有一个有序的数组，想要将一个元素插入到该数组中。
还要保证该数组是有序的。
本质：是如何获取该元素在数组中的位置。
*/
class ArrayTest
{
public static void main(String[] args)
{
int[] arr={2,4,5,7,19,32,45};
int index1=getIndex(arr,3);//此处结果为index=0，按下面来说，应该是作为脚标为0的值插进去，后面顺延，但应该是作为脚标为1的值插进去吧？？
System.out.println("index1="+index1);
int index2=getIndex(arr,8);//视频里的例子，结果为index=4，作为脚标为4的值插进去，后面顺延。
System.out.println("index2="+index2);
int index3=getIndex(arr,23);//结果为index=4，明明8与23插入的不是一个位置，为什么结果还是4？？
System.out.println("index3="+index3);
}
public static int getIndex(int[]arr,int key)
{
int min=0,max=arr.length-1,mid;
while(min<max)
{
mid=(max+min)>>1;
if(key>arr[mid])
min=mid+1;
else if (key<arr[mid])
max=mid-1;
else
return mid;
}
return min;//返回最小脚标min。如果返回的是max，运行后是一样的结果！
}
}

复制代码

今天在回顾毕老师day0407数组折半查找中的练习时，自己换了几个数字进去，发现结果都不对，代码和问题见上面，求大牛帮助。。。

Up↑Lee↗ · Up↑Lee↗

/*
练习：有一个有序的数组，想要将一个元素插入到该数组中。
还要保证该数组是有序的。
本质：是如何获取该元素在数组中的位置。
*/
class ArrayTest
{
public static void main(String[] args)
{
int[] arr={2,4,5,7,19,32,45};
int index1=getIndex(arr,3);
System.out.println("index1="+index1);
int index2=getIndex(arr,8);
System.out.println("index2="+index2);
int index3=getIndex(arr,23);
System.out.println("index3="+index3);
}
public static int getIndex(int[]arr,int key)
{
int min=0,max=arr.length-1,mid;
while(min<=max) //这里应该加一个=号！！！
{
mid=(max+min)>>1;
if(key>arr[mid])
min=mid+1;
else if (key<arr[mid])
max=mid-1;
else
return mid;
}
return min;
}
}

复制代码

错误之处已经指出，结果如下

tacyjay在路上 · tacyjay在路上

Up↑Lee↗ 发表于 2014-3-21 15:57
错误之处已经指出，结果如下

汗。。。。
本来以为看的够仔细了，刚刚又重新找到视频，在对halfsearch第二种讲解时，毕老师还特地强调了为什么有=号。。。。。
等号对查找问题几乎没有影响，但是对插入元素的问题影响可就不是一点两点了。。。{:3_65:}

没想到一个=号差了那么多，万分谢谢楼上的回答！！

马富林 · 马富林

话说知道了位置以后，数组怎么插入元素？

Up↑Lee↗ · Up↑Lee↗

tacyjay在路上发表于 2014-3-21 16:31
汗。。。。
本来以为看的够仔细了，刚刚又重新找到视频，在对halfsearch第二种讲解时，毕老师还特地强调 ...

哈哈你也刚准备么

love~陌 · love~陌

class Function00
{
public static void main(String[] args)
{
int [] array = new int []{1,2,3,4,5,6,7,8,9,0,11};
//排序前的数组遍历
print(array);
smart();
//数组中的最值
int max;
max=getMax(array);
System.out.println("max="+max);
smart();
//排序
//select(array);
bubble(array);
smart();
//排序后
print(array);
smart();
int key=6;
int index=halfsearch(array,key);
System.out.println("index="+index);
}
public static void smart()
{
System.out.println("^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^");
}
//定义一个函数，实现数组遍历的功能
public static void print(int[] array)
{
System.out.print("[");
for (int x=0;x<=array.length-1;x++ )
{
if(x!=array.length-1)
System.out.print(array[x]+", ");
else
System.out.println(array[x]+"]");
}
}
//定义一个函数，实现获取数组中元素的最大值
/*
1.获取最值需要进行比较，每一次比较都会有一个较大的值，因为该值不确定，通过一个变量进行存储
2.让数组中的每一个元素都喝这个变量的值进行比较
3.当所有的元素都比较完成，那么该变量中存储的就是数组中的最大值了
步骤：
1.定义变量，初始化为数组中的任意一个元素即可
2.通过循环语句对数组进行遍历
3.在遍历过程中定义判断条件，如果遍历到的元素比变量中的元素大，就赋值给该变量
需要定义一个功能来完成，以提高复用性
1.明确结果，数组中的最大元素 int
2.未知内容，一个数组 int[]
*/
//获取double类型数组的最大值，因为功能一致，所以定义相同函数名称，以重载形式存在
/*
public static double getMax(int[] array)
{
}
*/
//求最大值
public static int getMax(int[] array)
{
int max=array[0];
for (int x=1;x<array.length;x++)
{
if (max<array[x])
max=array[x];
}
return max;
}
//选择排序
public static void select(int [] array)//void没有返回值
{
for (int x=0;x<array.length-1;x++ )
{
for (int y=x+1;y<array.length;y++)
{
if (array[x]>array[y])
{
/*
int temp;
temp=array[x];
array[x]=array[y];
array[y]=temp;
*/
swap(array,x,y);
}
}
}
}
//冒泡排序
public static void bubble(int[]array)
{
for (int x=0;x<array.length-1;x++ )
{
for (int y=0;y<array.length-x-1;y++ )//-x：让每一次比较的元素减少；-1：避免角标越界
{
if(array[y]>array[y+1])
{
/*
int temp;
temp=array[y];
array[y]=array[y+1];
array[y+1]=temp;
*/
swap(array,y,y+1);
}
}
}
}
//位置置换功能的抽取封装
public static void swap(int [] array,int a,int b)
{
array[a]=array[a]^array[b];
array[b]=array[a]^array[b];
array[a]=array[a]^array[b];
}
//希尔排序》》最快的排序方式
//折半查找
public static int halfsearch(int [] array,int key)
{
int min,max,mid;
min=0;
max=array.length-1;
mid=(max+min)/2;
while (array[mid]!=key)
{
if (array[mid]<key)
min=mid+1;
else if (array[mid]>key)
max=mid-1;
if(min>max)
return -1;
mid=(min+max)/2;
}
return mid;
}
//ArrayIndexOutOfBoundsException: 3 ：操作数组时，访问到了数组中不存在的角标
//NullPointerException:空指针异常：当引用没有任何指向值为null的情况，该引用还在用于操作实体
}

复制代码

你可以参考一下我这个，这是我当时看毕老师视频的时候写的，这是草稿，未曾整理，代码保证是正确的，希望对你有帮助

tacyjay在路上 · tacyjay在路上

Up↑Lee↗ 发表于 2014-3-21 18:49
哈哈你也刚准备么

恩恩。。。速度太慢，得加紧时间了。。
加油哈。。

tacyjay在路上 · tacyjay在路上

马富林发表于 2014-3-21 18:29
话说知道了位置以后，数组怎么插入元素？

这个不知道。。不好意思。

帐号		自动登录	找回密码
密码			加入黑马

折半查找中元素插入数组中的问题，百思不得解，求助。。

评分

8 个回复

评分

点评