/**
New灬狼
2016年1月4日21:38:36
*/
/*
需求：基于一个有序数组，在数组中插入一个数，还要保证数组是有序的。
思路：
1，要保证插入这个数以后，数组还是有序，那就说明这个数插入的位置很重要；
2，要插入的这个数如果数组中有的话，再把这个数插入到那个数在数组中的位置，
原来数组中的数顺次后移一位，那么数组还是有序；
3，要确定数组有没有这个数，可以用halfSearch找一下，如果有直接返回角标；
4，还有一种情况就是数组中没有这个数，怎么确定这个插入的位置呢？
其实halfSearch如果没有找到要找的数时，min正好是要插入这个数的位置。
步骤：
1,新建ArrayTest06.java
2,利用halfSearch查找这个数以确定位置；
3，插入这个数；
4，遍历数组，看看是否还是有序的；
*/
class ArrayTest06
{
//定义遍历数组函数display
public static void display(int [] arr)
{
for (int x=0;x<arr.length ;x++ )
{
System.out.print(x+":"+arr[x]+"\t");
}
System.out.println("\n");
}
//定义要插入这个数的角标函数getIndex
public static int getIndex(int [] arr,int key)
{
int min=0;
int mid;
int max=arr.length-1;
while (min<=max)
{
mid=(min+max)>>1;
if (key>arr[mid])
{
min=mid+1;
}
else if (key<arr[mid])
{
max=mid-1;
}
else
return mid;
}
return min;
}
//测试
public static void main(String [] args)
{
int a=5,b=3;
int arr []={1,2,3,4,5,6,7,9,10};
display(arr);
int key=getIndex(arr,(a-b));
//System.out.println(key);
arr [key]=a-b;
display(arr);
//实际测试时，原来有的数组中有的数不会向后移位，是我写错了吗？
int key1=getIndex(arr,(a+b));
//System.out.println(key1);
//如果数组中没有这个数，而且这个数比数组中所有数都大，
//就会出现key1>arr.length,运行时就会出现角标越界的问题，怎么解？
arr [key1]=a+b;
display(arr);
}
}
|
|
收藏
淘帖
踩
