Created
April 24, 2024 20:18
-
-
Save Cubik65536/4062fc131b9d5b6b44dd6757eb9df593 to your computer and use it in GitHub Desktop.
Recursive Search in Java
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.ArrayList; | |
import java.util.Scanner; | |
class LinearSearch { | |
/** | |
* 线性搜索 | |
* @param list 要搜索的数组 | |
* @param target 要搜索的目标 | |
* @return 目标在数组中的索引,如果不存在则返回 -1 | |
*/ | |
public static int search(ArrayList<Integer> list, int target) { | |
for (int i = 0; i < list.size(); i++) { // 遍历数组 | |
if (list.get(i) == target) { // 如果找到目标 | |
return i; // 返回目标的索引 | |
} | |
} | |
return -1; // 如果循环完整结束了,则代表没有找到目标,返回 -1 | |
} | |
public static int recursiveSearch(ArrayList<Integer> list, int target, int index) { | |
if (index == list.size()) { | |
return -1; | |
} | |
if (list.get(index) == target) { | |
return index; | |
} | |
return recursiveSearch(list, target, index + 1); | |
} | |
} | |
class JumpSearch { | |
/** | |
* 跳跃搜索 | |
* @param list 要搜索的数组 | |
* @param target 要搜索的目标 | |
* @return 目标在数组中的索引,如果不存在则返回 -1 | |
*/ | |
public static int search(ArrayList<Integer> list, int target) { | |
int step = (int) Math.sqrt(list.size()); // 获取步长 | |
int idx; // 索引 | |
for (idx = 0; idx < list.size(); idx += step) { // 以步长为单位遍历数组 | |
if (list.get(idx) == target) { // 如果找到目标 | |
return idx; // 返回目标的索引 | |
} | |
if (list.get(idx) > target) { // 如果当前元素大于目标,则目标在当前元素之前,上次检查的元素之后 | |
break; // 结束以步长为单位的遍历 | |
} | |
} | |
for (int i = idx - step; i < idx; i++) { // 回退一个步长,回到上次检查的元素,遍历这个步长内的元素 | |
if (list.get(i) == target) { // 如果找到目标 | |
return i; // 返回目标的索引 | |
} | |
} | |
return -1; // 如果循环完整结束了,则代表没有找到目标,返回 -1 | |
} | |
public static int recursiveSearch(ArrayList<Integer> list, int target, int index, int step) { | |
if (index >= list.size() || list.get(index) > target) { | |
if (step == 1) { | |
return -1; | |
} | |
return recursiveSearch(list, target, index - step, 1); | |
} | |
if (list.get(index) == target) { | |
return index; | |
} | |
return recursiveSearch(list, target, index + step, step); | |
} | |
} | |
class BinarySearch { | |
/** | |
* 二分搜索 | |
* @param list 要搜索的数组 | |
* @param target 要搜索的目标 | |
* @return 目标在数组中的索引,如果不存在则返回 -1 | |
*/ | |
public static int search(ArrayList<Integer> list, int target) { | |
int low = 0; // 低位索引 | |
int high = list.size() - 1; // 高位索引 | |
while (low <= high) { // 当低位索引小于等于高位索引时,才有元素可以搜索 | |
int mid = (low + high) / 2; // 计算中间索引 | |
if (list.get(mid) == target) { // 如果找到目标 | |
return mid; // 返回目标的索引 | |
} else if (list.get(mid) < target) { // 如果中间元素小于目标,则目标在中间元素之后 | |
low = mid + 1; // 低位索引更新为中间索引加一,在中间元素之后的元素中搜索 | |
} else { // 如果中间元素大于目标,则目标在中间元素之前 | |
high = mid - 1; // 高位索引更新为中间索引减一,在中间元素之前的元素中搜索 | |
} | |
} | |
return -1; // 如果循环完整结束了,则代表没有找到目标,返回 -1 | |
} | |
public static int recursiveSearch(ArrayList<Integer> list, int target, int low, int high) { | |
if (low > high) { | |
return -1; | |
} | |
int mid = (low + high) / 2; | |
if (list.get(mid) == target) { | |
return mid; | |
} else if (list.get(mid) < target) { | |
return recursiveSearch(list, target, mid + 1, high); | |
} else { | |
return recursiveSearch(list, target, low, mid - 1); | |
} | |
} | |
} | |
public class Main { | |
public static void main(String[] args) { | |
ArrayList<Integer> list = new ArrayList<>(); | |
list.add(1); | |
list.add(1); | |
list.add(2); | |
list.add(3); | |
list.add(5); | |
list.add(8); | |
list.add(13); | |
list.add(21); | |
list.add(55); | |
list.add(77); | |
list.add(89); | |
list.add(101); | |
list.add(201); | |
list.add(256); | |
list.add(780); | |
list.add(1024); | |
list.add(65536); | |
list.add(66666); | |
System.out.println(list); | |
Scanner scanner = new Scanner(System.in); | |
System.out.print("Enter the target: "); | |
int target = scanner.nextInt(); | |
// int index = LinearSearch.search(list, target); | |
// int index = JumpSearch.search(list, target); | |
// int index = BinarySearch.search(list, target); | |
// int index = LinearSearch.recursiveSearch(list, target, 0); | |
int index = JumpSearch.recursiveSearch(list, target, 0, (int) Math.sqrt(list.size())); | |
// int index = BinarySearch.recursiveSearch(list, target, 0, list.size() - 1); | |
if (index == -1) { | |
System.out.println("Not Found"); | |
} else { | |
System.out.println("Found at index " + index); | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment