Skip to content

Instantly share code, notes, and snippets.

@Qubik65536

Qubik65536/Main.java

Last active May 7, 2024 15:21
Show Gist options
  • Save Qubik65536/602f821205723939ad7174dcfd9c3cd1 to your computer and use it in GitHub Desktop.
Save Qubik65536/602f821205723939ad7174dcfd9c3cd1 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. Qubik65536 revised this gist May 7, 2024. 1 changed file with 2 additions and 1 deletion.
    3 changes: 2 additions & 1 deletion Main.java
    View file
    Original file line number Diff line number Diff line change
    @@ -40,7 +40,8 @@ public static int search(ArrayList<Integer> list, int target) {
    }
    }

    for (int i = idx - step; i < idx; i++) { // 回退一个步长，回到上次检查的元素，遍历这个步长内的元素
    // 回退一个步长，回到上次检查的元素，遍历这个步长内的元素（或者直到数组末尾）
    for (int i = idx - step; i < idx && i < list.size(); i++) {
    if (list.get(i) == target) { // 如果找到目标
    return i; // 返回目标的索引
    }
  2. Qubik65536 created this gist Apr 10, 2024.
    116 changes: 116 additions & 0 deletions Main.java
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,116 @@
    package org.qianq.examples;

    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
    }
    }

    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
    }
    }

    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 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);

    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);

    if (index == -1) {
    System.out.println("Not Found");
    } else {
    System.out.println("Found at index " + index);
    }
    }
    }