//数组查找
class SearchTest
{
public static void main(String[] args)
{
//int[] arr = {2,5,8,4,6};
int [] arr = {3,5,6,8,12};
int index = halfSearch_1(arr,4);
System.out.println("index="+index);
}
//将一个数插入到数组中，插入后还要保证数组的有序
//折半查找，找出那个数应该对应的角标，折半查找数组必须是有序的
public static int halfSearch_1(int[] arr,int key)
{
int min=0;
int max=arr.length-1;
while (min<max)
{
int mid=(min+max)/2;
if(key>arr[mid])
min=mid+1;
else if(key<arr[mid])
max=mid-1;
else
return mid;
}
return min;//min的角标对应的就是要插入的位置
}
//折半查找
public static int halfSearch(int[] arr,int key )
{
int min=0,max= arr.length-1,mid=(min+max)/2;
while (key!=arr[mid])
{
if (key>arr[mid])
min=mid+1;
else if (key<arr[mid])
max=mid-1;
if (min>max)//目的值不存在，没找到
return -1;
mid = (min+max)/2;
}
//当循环的条件不满足时，不是找到了，就是不存在
return mid;
}
/*
public static int search(int[] arr,int key)
{
for (int x=0;x<arr.length ;x++ )
{
if (key==arr[x])
return x;
}
return -1;