递增数组的二分查找的递归和非递归算法

1.简单的函数调用，返回一个整形的数字的下标
import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;
public class FunctionTestUint {
public static void main(String[] args) {
int[] arr = new int[20];
Random rd = new Random();
for (int i = 0; i < arr.length; i++) {
arr[i] = rd.nextInt(100);
}
System.out.println(Arrays.toString(arr));
//数组排序
Arrays.sort(arr);
System.out.println(Arrays.toString(arr));
//数组元素的查找，找到指定元素，返回其下标，找不到返回-1；
//线性查找
int index = -1;
index = LinearSearch(arr,64);
System.out.println(index);
}
private static int LinearSearch(int[] arr, int i) {
for (int i1 = 0; i1 < arr.length; i1++) {
if (arr[i1] == i) {
return i1;
}
}
return -1;
}
index = Arrays.binarySearch(arr, 1, 2, 3);
2.(1)递增数组的二分查找,非递归算法
import java.util.Arrays;
import java.util.Random;
class Array{
//用来存储元素
private int[] arr;
//数组大小
private int size;
//无参构造函数
public Array(){
this(10);
}
//有参构造函数，初始化数组
public Array(int size){
Random rd=new Random();
this.arr=new int[size];
for (int i = 0; i < arr.length; i++) {
arr[i]=rd.nextInt(20);
}
Arrays.sort(arr);
}
//递增数列二分查找非递归算法
import java.util.Arrays;
import java.util.Random;
class Array{
//用来存储元素
private int[] arr;
//数组大小
private int size;
//无参构造函数
public Array(){
this(10);
}
//有参构造函数，初始化数组
public Array(int size){
Random rd=new Random();
this.arr=new int[size];
for (int i = 0; i < arr.length; i++) {
arr[i]=rd.nextInt(20);
}
Arrays.sort(arr);
}
//递增数列二分查找非递归算法
public int binarySearch(int data){
int head=0;
int tail=arr.length-1;
int mid=0;
while(tail>=head) {
mid = (tail + head) / 2;//求出中间值
if (arr[mid] == data) {//相等，直接返回下标
return mid;
} else if (arr[mid] > data) {//arr[mid]>data,则arr[mid]后所有数字都大于data，tail = mid - 1;
tail = mid - 1;
} else { //同上，head=mid+1;
head = mid + 1;
}
}
return -1;
}
//递增数列递归算法
public int binarySearch1(int[] arr, int data) {
return binarySearch1(arr, 0, arr.length-1, data) ;
}
public int binarySearch1(int[] arr, int i, int j, int data) {
if(i > j){ // 递归结束的条件，表示data值不存在
return -1;
}
int mid = (i+j) / 2;
if(arr[mid] == data){ // 当前递归结束的条件
return mid;
}
if(arr[mid] > data){ // i <-> mid-1
return binarySearch1(arr, i, mid-1, data) ;
} else { // mid+1 <-> j
return binarySearch1(arr, mid+1, j, data);
}
}
}
public class practise {
public static void main(String[] args) {
Array list = new Array();
int index = 0;
index = list.binarySearch(10);
System.out.println(index);
int[] newarr=new int[10];
Random rd=new Random();
for (int i = 0; i < newarr.length; i++) {
newarr[i]=rd.nextInt(20);
}
Arrays.sort(newarr);
System.out.println(list.binarySearch1(newarr,10));
}
}