/*
目的：练习折半查找，熟练掌握折半查找的原理和操作方法；
需求：给出一个有序数组，在数组中插入一个元素，使得插入后的数组仍然有序，求出插入元素的位置；
思路：使用随机函数给出一个长度为20的数组，使用排序函数将数组变成一组有序的数组，然后利用折半查找的原理找出元素应该插入的位置；
步骤：使用随机函数产生一个长度为20 的随机数组；
使用冒泡排序函数将该数组进行排序，使得原数组变成一个有序数组；
利用折半查找原理找到与目标值相同的数字，或者返回不能继续的端点比较坐标；
返回值即我们要插入的位置；
*/
import java.util.Scanner;
class InsertSearch
{
public static void main(String[] args)
{
int n;
System.out.print("请输入数组的长度：");
n = inputInt();//整数输入器
int[] arr = new int[n];
arr = productArray(n);//数组生成器
printArray(arr);
newline(1);//换行器
System.out.println("排序后的数组为：");
Sort(arr);//排序
printArray(arr);
newline(1);
int key = 321;
int x = insertSearch(arr,key);
System.out.println("321在数组的插入位置为："+x);
}
//整数输入器
public static int inputInt()
{
Scanner in = new Scanner(System.in);
int x = in.nextInt();
in.close();
return x;
}
//数组生成器
public static int[] productArray(int n)
{
int[] arr = new int[n];
for (int x = 0;x < n ;x++ )
{
arr[x] = (int)(Math.random()*1000);
}
return arr;
}
//数组输出器
public static void printArray(int[] arr)
{
System.out.print("[ ");
for (int x = 0;x < arr.length ;x++ )
{
if(x < arr.length-1)
System.out.print(arr[x]+" ");
else
System.out.print(arr[x]+" ]");
}
}
//设计排序函数
public static void Sort(int[] arr)
{
for (int x = 0;x<arr.length-1 ;x++ )
{
for (int y = 0;y<arr.length-x-1 ;y++ )
{
if(arr[y] > arr[y+1])
{
int temp = arr[y];
arr[y] = arr[y+1];
arr[y+1] = temp;
}
}
}
}
/*
//折半查找法1
public static int insertSearch(int[] arr,int key)
{
int min ,max , mid;
min = 0;
max = arr.length-1;
mid = (min + max)/2;
while (arr[mid] != key)
{
if(key > arr[mid])
min = mid + 1;
else if (key < arr[mid])
max = mid - 1;
if(min > max)
return mid;
mid = (min + max)/2;
}
return mid;
}
*/
//折半查找法2
public static int insertSearch(int[] arr,int key)
{
int min = 0,max = arr.length-1,mid = 0;
while(min <= max)
{
mid = (max + min)/2;
if(key > arr[mid])
min = mid + 1;
else if(key < arr[mid])
max = mid - 1;
else
return mid;
}
return mid;
}
//换行器
public static void newline(int x)
{
while(x >=1)
{
System.out.println();
x--;
}
}
}
/*
运行结果：
请输入数组的长度：10
[ 115 233 684 853 135 998 532 747 604 882 ]
排序后的数组为：
[ 115 135 233 532 604 684 747 853 882 998 ]
321在数组的插入位置为：3
请输入数组的长度：10
[ 694 510 487 643 297 974 675 591 688 201 ]
排序后的数组为：
[ 201 297 487 510 591 643 675 688 694 974 ]
321在数组的插入位置为：2
|
|
收藏
淘帖
踩
