/*练习插入一个数进一个数组,并保证数组有序*/
public class HalfSeach
{
public static int halfSeach(int[] n,int key)
{
int min=0,max=n.length-1,mid;
mid=(min+max)>>1;
while(n[mid]!=key)
{
if(key>n[mid])
min=mid+1;
else if(key<n[mid]) max=mid-1;
mid=(min+max)>>1;
while(min>max) return -1;
} return mid;
}
public static int halfSeach2(int[] n,int key)
{
int min=0,max=n.length-1;
int mid=(min+max)>>1;
while(min<=max)
{ if(key>n[mid]) min=mid+1;
else if(key<n[mid]) max=mid-1;
else return mid; //这里的mid'包含数组只有一个数和插入的数和数组中的数相同的情况,这里就是插入的下标值;
mid=(min+max)>>1;
} return -1; //这里将-1改为min值,就是插入数的下标值。
}
/*public static void inserNumber(int[] n,int inserNum) java中数组不可扩容,要通过collection来做ArrayList.
{
int min=0,max=n.length-1,mid;
mid=(min+max)/2;
while(min==max)
{
if(inserNum>n[mid]) min=mid+1;
else if(inserNum<n[mid]) max=mid-1;
mid=(min+max)>>1;
break;
}int x=n.length+1;
if(n[mid]>inserNum) {for(int i=x;i>mid;i--) {n[i]=n[i-1];n[mid]=inserNum;}}
else if(n[mid]<=inserNum) {for(int i=n.length;i>mid+2;i--){n[i]=n[i-1];n[mid+1]=inserNum;}}
}*/
public static void printArray(int[] n)
{ System.out.print("[");
for(int i=0;i<n.length;i++)
{ if(i!=n.length-1)
System.out.print(n[i]+", ");
else System.out.print(n[i]);
} System.out.println("]");
}
public static void main(String[] args)
{
int[] n={1,3,4,5,7,9,12,23,45,67,90,123};
System.out.println(halfSeach2(n,23));
System.out.println(halfSeach2(n,231));
inserNumber(n,10);
printArray(n);
}
} |