在一个有序数组中利用折半查找的思想，来插入一个元素... - 黑马程序员技术交流社区

<p>class Demo{
static int halfsearch(int arr[],int key){
int min=0;
int max=arr.length;
int mid=(min+max)/2;
while(min<=max){
mid=(min+max)/2;
if(key>arr[mid])
{
min=mid+1;
}
else if(key<arr[mid])
{
max=mid-1;
}
else
return mid;
}
return mid;
}
/**
* 在一个有序数组中利用折半查找的思想，来插入一个元素，使得插入后的数组依然有序，代码实现返回插入的位置。
* */
public static void main(String args[]){
int arr[]={1,2,4,5,6,7,9};
System.out.print(halfsearch(arr,-1));//这程序有个问题就是当要插入的数比数组中的最大元素大时，会发生数组角标越界的情况
}
}</p><p>要如何修改呢？
</p>

复制代码

class Demo
{
public static void main(String[] args)
{
int[] arr = new int[]{1,6,9,11,18,54,60,66,90};
System.out.println("insert 19 to array:");
printArr(arr);
int[] newArr = insert( arr, 100 );
printArr( newArr );
}
//打印一个数组
public static void printArr(int[] arr)
{
for (int x = 0; x<arr.length; x++ )
{
if (x == arr.length - 1)
{
System.out.println(arr[x]);
break;
}
System.out.print(arr[x] + "\t");
}
}
//在数组中插入一个元素
public static int[] insert( int[] arr, int insertKey )
{
int loc, mid;
int[] newArr = new int[arr.length + 1];
mid = locFind( arr, insertKey );
//插入新元素操作，分三种情况，在首部，在尾部，在中间
if (insertKey < arr[0])//在首部
{
newArr[0] = insertKey;
for ( int x = 1; x <= arr.length; x++ )
{
newArr[x] = arr[x - 1];
}
}
else if (insertKey > arr[arr.length - 1])//在尾部
{
int x;
for (x = 0 ; x < arr.length ; x++ )
{
newArr[x] = arr[x];
}
newArr[x] = insertKey;
}
else//在中间
{
for ( loc = 0; loc <= mid; loc++ )//插入位之前的元素赋值给新数组
{
newArr[loc] = arr[loc];
}
newArr[loc] = insertKey;
for ( loc++; loc < newArr.length; loc++ )//插入位之后的元素赋值给新数组
{
newArr[loc] = arr[loc - 1];
}
}
return newArr;
}
//用折半查找法找到元素应该插入数组的位置并返回
public static int locFind( int[] arr, int insertKey )
{
int min, mid, max;
min = 0;
max = arr.length;
mid = ( max + min ) / 2;
while ( min < max )
{
if ( insertKey > arr[mid] )
{
min = mid + 1;
}
else if ( insertKey < arr[mid] )
{
max = mid - 1;
}
mid = ( max + min ) / 2;
}
return mid;
}
}

复制代码