Searching: linear and binary · ⁨查找:线性查找与二分查找⁩ — Java for AP CS A

English

Finding a value

A common job is to search: is a value in an array, and where?
The usual answer is the index where we found it, or -1 if it is not there.
We learn two ways: linear search (works on any array) and binary search (needs a sorted array, but is much faster).

中文

查找一个值

一个常见的工作是查找(search):某个值在不在数组里,以及在哪里?
通常的答案是我们找到它的那个下标(index),或者如果不在就返回 -1。
我们学习两种方法:线性查找(linear search,适用于任何数组)和二分查找(binary search,需要已排序的数组,但快得多)。

English

Linear search

Look at each item from index 0 to the end.
If the item equals the target, return its index right away.
If the loop finishes with no match, return -1.

中文

线性查找

从下标 0 到末尾,逐个查看每个元素。
如果这个元素等于目标值,就立刻返回它的下标。
如果循环结束都没有匹配,就返回 -1。

public class Main {
    public static void main(String[] args) {
        int[] a = {4, 8, 15, 16, 23};
        int target = 15;
        int found = -1;
        for (int i = 0; i < a.length; i++) {
            if (a[i] == target) {
                found = i;
                break;       // stop early, we have it
            }
        }
        System.out.println(found);   // 2
    }
}

English

How fast is linear search?

In the worst case (the value is last, or missing) it checks every item.
For a list of n items that is up to n checks. We call this linear time.
For small arrays this is totally fine. For huge sorted arrays we can do better.

中文

线性查找有多快?

在最坏的情况下(值在最后,或者根本不存在),它会检查每一个元素。
对于有 n 个元素的列表,这最多是 n 次检查。我们把这叫作线性(linear)时间。
对于小数组这完全没问题。但对于很大的已排序数组,我们可以做得更好。

English

Binary search needs a sorted array

Binary search only works when the array is already sorted (small to large).
It checks the middle item, then throws away half the array each step.
That is much faster: a million items take about 20 checks, not a million.

中文

二分查找需要已排序的数组

二分查找只在数组已经排好序(从小到大)时才有效。
它检查中间的元素,然后每一步丢掉一半的数组。
这快得多:一百万个元素大约只需要 20 次检查,而不是一百万次。

English

The binary search idea

Keep two bounds: low (start) and high (end).
Look at the middle index mid = (low + high) / 2.
If a[mid] equals the target, return mid.
If a[mid] is too small, the target must be on the right, so set low = mid + 1.
If a[mid] is too big, the target must be on the left, so set high = mid - 1.
Stop when low passes high; then the value is not there, return -1.

中文

二分查找的思路

保留两个边界:low(开始)和 high(结束)。
查看中间的下标 mid = (low + high) / 2。
如果 a[mid] 等于目标值,返回 mid。
如果 a[mid] 太小,目标值一定在右边,所以设 low = mid + 1。
如果 a[mid] 太大,目标值一定在左边,所以设 high = mid - 1。
当 low 超过 high 时停止;这时值不存在,返回 -1。

public class Main {
    public static void main(String[] args) {
        int[] a = {2, 5, 8, 12, 16, 23, 38};   // sorted!
        int target = 16;

        int low = 0;
        int high = a.length - 1;
        int found = -1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (a[mid] == target) {
                found = mid;
                break;
            } else if (a[mid] < target) {
                low = mid + 1;     // go right
            } else {
                high = mid - 1;    // go left
            }
        }
        System.out.println(found);   // 4
    }
}

English

When a value is missing

Both searches return -1 when the target is not in the array.
For binary search, the loop ends when low > high — the bounds have crossed, so there is nowhere left to look.
Always handle the -1 case in code that calls a search.

中文

当某个值不存在时

当目标值不在数组里时,两种查找都返回 -1。
对于二分查找,当 low > high 时循环结束 —— 边界交叉了,所以没有地方可以再找了。
在调用查找的代码里,一定要处理 -1 这种情况。

public class Main {
    public static void main(String[] args) {
        int[] a = {2, 5, 8, 12};   // sorted
        int target = 7;            // not in the array

        int low = 0;
        int high = a.length - 1;
        int found = -1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (a[mid] == target) {
                found = mid;
                break;
            } else if (a[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        System.out.println(found);   // -1
    }
}

English

Common mistakes

Binary search needs a sorted array.
Linear search is O(n); binary is O(log n).

中文

常见错误

二分查找需要已排序的数组。
线性查找是 O(n);二分是 O(log n)。

English

Now you try

Each task pre-fills the class skeleton — write your code inside main, or complete the method shown.
Press Run to compile and run, then Check answer.
Your code compiles and runs on the server, so even the first run is fast.

中文

现在轮到你

每个任务都已经填好了类的骨架 —— 把你的代码写在 main 里面,或者补全给出的方法。
按运行来编译并运行,然后按检查答案。
你的代码在服务器上编译并运行,所以第一次运行也很快。

Explore · ⁨探索⁩

Linear vs binary search · ⁨线性 vs 二分查找⁩

Binary search halves the range each step — far fewer checks. · ⁨二分查找每步把范围减半——检查次数少得多。⁩

Complete linearSearch(int[] a, int target). Return the index of the first item equal to target, or -1 if it is not in the array. Check items from index 0 upward. · ⁨完成 linearSearch(int[] a, int target)。返回第一个等于 target 的元素的下标,如果数组里没有就返回 -1。从下标 0 开始向后检查。⁩

public class SearchUtil {
    // Return the index of target, or -1 if not found.
    public static int linearSearch(int[] a, int target) {
        return -1;   // change this
    }
}

Click Run to see the output here. · ⁨点击“运行”查看此处输出。⁩

Complete binarySearch(int[] a, int target) for a sorted array. Use low/high bounds and check the middle each step. Return the index of target, or -1 if it is missing. · ⁨为一个已排序的数组完成 binarySearch(int[] a, int target)。使用 low/high 边界,每一步检查中间的元素。返回 target 的下标,如果不存在就返回 -1。⁩

public class SearchUtil {
    // Binary search on a sorted array. Return index or -1.
    public static int binarySearch(int[] a, int target) {
        int low = 0;
        int high = a.length - 1;
        // your loop here
        return -1;
    }
}

Click Run to see the output here. · ⁨点击“运行”查看此处输出。⁩

Complete countOccurrences(int[] a, int target) that returns how many times target appears in a (a linear scan). Return 0 if it never appears. · ⁨完成 countOccurrences(int[] a, int target),返回 target 在 a 中出现的次数(线性扫描)。如果从不出现就返回 0。⁩

public class SearchUtil {
    // Count how many times target appears in a.
    public static int countOccurrences(int[] a, int target) {
        return 0;   // change this
    }
}

Click Run to see the output here. · ⁨点击“运行”查看此处输出。⁩

Searching: linear and binary · ⁨查找:线性查找与二分查找⁩

Finding a value

查找一个值

Linear search

线性查找

How fast is linear search?

线性查找有多快?

Binary search needs a sorted array

二分查找需要已排序的数组

The binary search idea

二分查找的思路

When a value is missing

当某个值不存在时

Common mistakes

常见错误

Now you try

现在轮到你

Linear vs binary search · ⁨线性 vs 二分查找⁩

Handout

Log in or create account · ⁨登录或创建账户⁩

Your subject · ⁨你的学科⁩

All sections · ⁨所有板块⁩

Feedback & help · ⁨反馈与帮助⁩