给定一个有序的数组，如果往该数组中存贮一个元素，并保证这个数组还是有序的，那么这个元素存储的角标该如何获取。
//这是一个有序的数组，又是关于位置查找问题，自然想到数组的拆半查找。
class Arr
{
public static void main(String [] args)
{
int [] arr = {7,32,55,67,75,95};
int index = getKeyIndex(arr,56);
System.out.print("index="+index);
}
//有结果 角标 int型
//有两个参数 哪个数组 要在该数组中存储的元素
public static int getKeyIndex(int [] arr, int key)
{
int min = 0;
int max = arr.length-1;
int mid = (min + max)/2;
while(max >= min) //这样就会有折半的可能
{
mid = (min + max)>>1; //右移一位 就是(max+min)除以2的一次幂
if(key > arr[mid])
{
min = mid + 1;
}
else if(key < arr[mid])
{
max = mid - 1;
}
else
{
return mid;
}
}
return min;
}
}
|
|
收藏
淘帖
踩
