目录
二分查找:
分块查找:(有规律模块)
分块排序:(无规律模块)
二分查找:
import javax.swing.*;
import java.util.Scanner;
public class Binary_Search {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int[] arr = {1,2,3,4,5,6,7,8,9,10,11};
int num = sc.nextInt();
System.out.println(BinarySearch(arr, num));
}
private static int BinarySearch(int[] arr, int num) {
int left = 0;
int right = arr.length - 1;
while(true){
if(left > right){
return -1;
}
int mid = (left + right) / 2;
if(arr[mid] < num){
left = mid + 1;
}
else if(arr[mid] > num){
right = mid - 1;
}
else{
return mid;
}
}
}
}
分块查找:(有规律模块)
import java.util.Scanner;
public class Block_algorithm {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
//有规律的模块
int[] arr = {16,5,9,12,21,18,
32,23,37,26,45,34,
50,48,61,52,73,66};
Block b1 = new Block(21,0,5);
Block b2 = new Block(45,6,11);
Block b3 = new Block(73,12,17);
Block[] blockArr = {b1,b2,b3};
System.out.println("输入查找的数字:");
int num = sc.nextInt();
System.out.println(getindex(arr,blockArr, num));
}
private static int getindex(int[] arr , Block[] blockArr , int num) {
int index = findIndexBlock(blockArr,num);
if(index == -1)
return -1;
for(int i = blockArr[index].getStartindex();i <= blockArr[index].getEndindex();i++){
if(arr[i] == num)
return i;
}
return -1;
}
private static int findIndexBlock(Block[] blockArr , int num){
for(int i = 0;i < blockArr.length;i++){
if(num <= blockArr[i].getMax()){
return i;
}
}
return -1;
}
}
//下面是标准JavaBean类,为了简洁不予展现全部
class Block{
private int max;
private int startindex;
private int endindex;
//~
}
分块查找:(无规律模块)
import java.util.Scanner;
public class Block_algorithm2 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("输入待查找的数据:");
int num = sc.nextInt();
//无规律模块
int[] arr = {27,22,30,40,36,
13,19,16,20,
7,10,
43,50,48};
Block2 b1 = new Block2(22,40,0,4);
Block2 b2 = new Block2(13,20,5,8);
Block2 b3 = new Block2(7,10,9,10);
Block2 b4 = new Block2(43,50,11,13);
Block2[] block2Arr = {b1,b2,b3,b4};
System.out.println(getindex(arr, block2Arr, num));
}
private static int getindex(int[] arr, Block2[] block2Arr, int num) {
int index = findIndexBlock2(block2Arr,num);
if(index == -1) return -1;
for(int i = block2Arr[index].getStartindex();i <= block2Arr[index].getEndindex();i++)
{
if(arr[i] == num)
return i;
}
return -1;
}
private static int findIndexBlock2(Block2[] block2Arr, int num) {
for(int i = 0;i < block2Arr.length;i++){
if(num >= block2Arr[i].getMin() && num <= block2Arr[i].getMax())
{
return i;
}
}
return -1;
}
}
//下面代码为标准JavaBean类,为了简洁就不特意展现
class Block2{
private int min;
private int max;
private int startindex;
private int endindex;
//~
}