1、设计一个交互界面（例如菜单）供用户选择，如果可能，最好是一个图形化用户界面；
2、能够人工输入或随机产生一个长度为n的整数数组，要求数组任意两个元素都互不相同；
3、设计一个算法判断要求2中产生的整数数组是否为或未排序（输出0）、升序（输出1）、降序（输出2）、先升后降（输出3）、或先降后升（输出4）状态；
4、给定某具体元素，使用顺序检索算法判断该具体元素是否出现在要求2中产生的数组中，并统计关键字比较的次数；
5、给定某具体元素，使用二分检索算法判断该具体元素是否出现在要求2中产生的升序或降序的数组中，并统计关键字比较的次数；
6、给定某具体元素，使用三分检索算法判断该具体元素是否出现在要求2中产生的升序或降序的数组中，并统计关键字比较的次数；
7、给定先升后降（或先降后升）数组，使用二分检索思路查找该数组的最大值（或最小值）。
import java.util.Random;
import java.util.Scanner;
public class Retrieval {
//自动创建数组
public static int[] randomArray(int min, int max, int n) {
int len = max - min + 1;
if (max < min || n > len) {
return null;
}
//初始化给定范围的待选数组
int[] source = new int[len];
for (int i = min; i < min + len; i++) {
source[i - min] = i;
}
int[] result = new int[n];
Random rd = new Random();
int index = 0;
for (int i = 0; i < result.length; i++) {
//待选数组0到(len-2)随机一个下标
index = Math.abs(rd.nextInt() % len--);
//将随机到的数放入结果集
result[i] = source[index];
//将待选数组中被随机到的数，用待选数组(len-1)下标对应的数替换
source[index] = source[len];
}
return result;
}
//手动创建数组
public static int[] artificialArray(int n) {
int[] result = new int[n];
Scanner sc = new Scanner(System.in);
for (int i = 0; i < n; i++) {
System.out.println("请输入数组的第" + (i + 1) + "的值：");
result[i] = sc.nextInt();
}
return result;
}
//判断数组是否为升序
public static boolean isUpSort(int[] array) {
for (int i = 0; i < array.length - 1; i++) {
if (array[i] > array[i + 1]) {
return false;
}
}
return true;
}
//判断数组是否为降序
public static boolean isDownSort(int[] array) {
for (int i = 0; i < array.length - 1; i++) {
if (array[i] < array[i + 1]) {
return false;
}
}
return true;
}
//得到数组最大值下标
public static int getMaxIndex(int[] arr) {//得到数组最大值的下标
int max = arr[0];
int max_index = 0;
for (int x = 1; x < arr.length; x++) {//注意这里不要越界
if (arr[x] > max) {
max = arr[x];
max_index = x;
}
}
return max_index;
}
//得到数组最小值下标
public static int getMinIndex(int[] arr) {//得到数组最小值的下标
int min = arr[0];
int min_index = 0;
for (int x = 1; x < arr.length; x++) {//注意这里不要越界
if (arr[x] < min) {
min = arr[x];
min_index = x;
}
}
return min_index;
}
//判断数组为何种类型算法
public static int arraySortAlgorithm(int[] arr) {
int result = 0;//乱码序号
int maxIndex = getMaxIndex(arr);//得到最大值数组下标
int minIndex = getMinIndex(arr);//得到最小值数组下标
if (maxIndex == arr.length - 1 && minIndex == 0) {
if (isUpSort(arr)) {
System.out.println("为升序数组");
result = 1;
} else {
System.out.println("为乱序数组");
}
} else if (maxIndex == 0 && minIndex == arr.length - 1) {
if (isDownSort(arr)) {
System.out.println("为降序数组");
result = 2;
} else {
System.out.println("为乱序数组");
}
} else if (0 < minIndex && minIndex < arr.length - 1) {
int[] downArr = new int[minIndex + 1];
for (int i = 0; i < minIndex + 1; i++) {
downArr[i] = arr[i];
}
int[] upArr = new int[arr.length - minIndex];
for (int i = 0; i < arr.length - minIndex; i++) {
upArr[i] = arr[minIndex + i];
}
if (isDownSort(downArr) && isUpSort(upArr)) {
System.out.println("为先降序后升序数组");
result = 3;
} else {
System.out.println("为乱序数组");
}
} else if (0 < maxIndex && maxIndex < arr.length - 1) {
int[] upArr = new int[maxIndex + 1];
for (int i = 0; i < maxIndex + 1; i++) {
upArr[i] = arr[i];
}
int[] downArr = new int[arr.length - maxIndex];
for (int i = 0; i < arr.length - maxIndex; i++) {
downArr[i] = arr[maxIndex + i];
}
if (isDownSort(downArr) && isUpSort(upArr)) {
System.out.println("为先升序后降序数组");
result = 4;
} else {
System.out.println("为乱序数组");
}
}
else {
System.out.println("为乱序数组");
}
return result;
}
//顺组检索
public static int arrayOrderSearch(int[] arr,int tag){
for (int i = 0; i arr[high]) {
System.out.println("目标元素没有出现在该数组中");
return 0;
}
while (low <= high) {
middle = (low + high) / 2;
++i;
if (arr[middle] > tag) {
high = middle - 1;
} else if (arr[middle] < tag) {
low = middle + 1;
} else if (arr[middle]==tag){
System.out.println("目标元素出现在该数组中");
return i + 2;
}
}
} else if (isDownSort(arr)) {
if (tag > arr[low] || tag < arr[high]) {
System.out.println("目标元素没有出现在该数组中");
return 0;
}
while (low >= high) {
middle = (low + high) / 2;
++i;
if (arr[middle] < tag) {
high = middle - 1;
} else if (arr[middle] > tag) {
low = middle + 1;
} else if (arr[middle]==tag){
System.out.println("目标元素出现在该数组中");
return i + 2;
}
}
} else {
System.out.println("该数组不符合升序或降序要求");
return -1;
}
System.out.println("目标元素不在数组当中");
return i+2;
}
//三分检索升、降序数组
public static int arrayTernarySearch(int[] arr,int tag){
int i = 0;
int left = 0;
int right = arr.length - 1;
if (isUpSort(arr)) {
if (tag < arr[left] || tag > arr[right]) {
System.out.println("目标元素没有出现在该数组中");
return 0;
}
while (left < right) {
int midl = left + (right - left) / 3;
int midr = right - (right - left) / 3;
i++;
if (arr[midl] > tag) {
right = midl - 1;
} else if (arr[midr] < tag) {
left = midr + 1;
} else {
System.out.println("目标元素出现在该数组中");
return i + 2;
}
}
} else if (isDownSort(arr)) {
if (tag > arr[left] || tag < arr[right]) {
System.out.println("目标元素没有出现在该数组中");
return 0;
}
while (left < right) {
int midl = left + (right - left) / 3;
int midr = right - (right - left) / 3;
i++;
if (arr[midl] < tag) {
right = midl - 1;
} else if (arr[midr] > tag) {
left = midr + 1;
} else {
System.out.println("目标元素出现在该数组中");
return i + 2;
}
}
} else {
System.out.println("该数组不符合升序或降序要求");
return -1;
}
return -1;
}
//二分检索求先升后降数组最大值
public static int arrayUptoDownBinarySearchMax(int[] arr){
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1]) {
return arr[mid];
} else if (arr[mid] < arr[mid - 1]) {
right = mid - 1;
} else if (arr[mid] < arr[mid + 1]) {
left = mid + 1;
}
}
return -1;
}
//二分检索求先降后升数组最小值
public static int arrayDowntoUpBinarySearchMin(int[] arr){
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] < arr[mid - 1] && arr[mid] < arr[mid + 1]) {
return arr[mid];
} else if (arr[mid] > arr[mid - 1]) {
right = mid - 1;
} else if (arr[mid] > arr[mid + 1]) {
left = mid + 1;
}
}
return -1;
}
//主函数
public static void main(String[] args) {
int con = 1;
int[] result = arrayCreate();
Scanner s = new Scanner(System.in);
System.out.println("请输入检索目标元素");
int tag = s.nextInt();
do {
System.out.println("1、判断数组类型");
System.out.println("2、顺序查找目标元素");
System.out.println("3、二分法查找目标元素");
System.out.println("4、三分法查找目标元素");
System.out.println("5、二分法先升后降数组找最大值");
System.out.println("6、二分法先降后升数组找最小值");
int chose =s.nextInt();
switch (chose){
case 1:
System.out.println(arraySortAlgorithm(result));
break;
case 2:
System.out.println("顺序查找目标元素次数为："+arrayOrderSearch(result, tag));
break;
case 3:
System.out.println("二分法查找目标元素次数为："+arrayBinarySearch(result, tag));
break;
case 4:
System.out.println("三分法查找目标元素次数为："+arrayTernarySearch(result, tag));
break;
case 5:
System.out.println("二分法先升后降数组找最大值为："+arrayUptoDownBinarySearchMax(result));
break;
case 6:
System.out.println("二分法先降后升数组找最小值为："+arrayDowntoUpBinarySearchMin(result));
break;
}
System.out.println("是否返回首页？（1是，0退出程序）");
con=s.nextInt();
} while (con == 1);
}
}
判断数组为升序、降序、升序to降序、降序to升序核心思想：
升序、降序没什么好说的for循环匹配就可以了，代码主要是用后一个元素比前一个元素大（小）来判断，是否单调递增（减），主要还是聊一聊先升后降和先降后升。
核心思想：
由此可以先得到数组的最大和最小值，此时需要约束判断该数组的大致走向
1：最大值在数组首尾之间，大致走向为先升后降
if (0 < maxIndex && maxIndex < arr.length - 1)
2：最小值在数组首尾之间，大致走向为先降后升
if (0 < minIndex && minIndex < arr.length - 1)
之后以最大值（最小值）为轴将数组切开，分段来判断。如果两个分段都为单调递增（递减），则可以判断为符合条件，反之可判断为乱序数组。
