折半查找中元素插入数组中的问题，百思不得解，求助。。 - 黑马程序员技术交流社区

/*
练习：有一个有序的数组，想要将一个元素插入到该数组中。
还要保证该数组是有序的。
本质：是如何获取该元素在数组中的位置。
*/
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，运行后是一样的结果！
}
}

复制代码

/*
练习：有一个有序的数组，想要将一个元素插入到该数组中。
还要保证该数组是有序的。
本质：是如何获取该元素在数组中的位置。
*/
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;
}
}

复制代码

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的情况，该引用还在用于操作实体
}

复制代码