Searching: linear and binary · ⁨การค้นหา: Linear และ 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).

ไทย

การหาค่าค่าหนึ่ง

งานทั่วไปคือการ ค้นหา: มีค่าอยู่ใน array หรือไม่ และอยู่ที่ ตำแหน่ง ไหน?
คำตอบทั่วไปคือ index ที่เราพบมัน, หรือ -1 ถ้ามันไม่ได้อยู่ที่นั่น
เราเรียนวิธีการสองแบบ: linear search (ใช้ได้กับ array ใดๆ) และ binary search (ต้องใช้ array ที่ เรียงลำดับแล้ว แต่เร็วมาก)

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.

ไทย

การค้นหาแบบเชิงเส้น

ดูแต่ละรายการตั้งแต่ index 0 ไปจนถึงปลายสุด
หากรายการเท่ากับเป้าหมาย ให้กลับคืน index ของมันทันที
หากลูปจบโดยไม่พบสิ่งที่ตรงกัน ให้กลับคืน -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.

ไทย

Linear search เร็วแค่ไหน?

ในกรณีแย่ที่สุด (ค่านั้นอยู่ในสุดท้ายหรือไม่มีอยู่เลย) มันจะตรวจสอบ ทุก รายการ
สำหรับรายการขนาด n จะใช้การตรวจสอบสูงสุด n ครั้ง เราเรียกนี่ว่าเวลาแบบ linear
สำหรับ array ขนาดเล็กวิธีนี้ถือว่าโอเค但对于巨大的已排序数组，我们可以做得更好。

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.

ไทย

Binary search ต้องใช้ array ที่เรียงลำดับแล้ว

Binary search จะทำงานได้ก็ต่อเมื่อ array被排序好（从小到大）。
มันตรวจสอบรายการ ตรงกลาง จากนั้นทิ้ง array ครึ่งหนึ่ง ในแต่ละขั้นตอน
วิธีนี้เร็วกว่ามาก: รายการหนึ่งล้านรายการใช้เวลาตรวจสอบประมาณ 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.

ไทย

ความคิดเรื่อง Binary search

รักษาขอบเขตสองจุด: low (เริ่มต้น) และ high (สิ้นสุด)
ดูที่ middle index 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 เมื่อเป้าหมายไม่อยู่ใน array
สำหรับ binary search ลูปจะจบเมื่อ 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).

ไทย

ข้อผิดพลาดที่พบบ่อย

Binary search ต้องใช้ array ที่ เรียงลำดับแล้ว
Linear search คือ O(n); binary คือ 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.

ไทย

ลองดูเลย

Each task เติม skeleton class ไว้ล่วงหน้า — เขียนโค้ดของคุณ ภายใน main, หรือเติมเต็ม method ที่แสดง
กด Run เพื่อ compile และ run, แล้วกด Check answer
โค้ดของคุณ compile และ run บน server, ดังนั้นแม้การ run ครั้งแรกก็เร็ว

Explore · ⁨สำรวจ⁩

Linear vs binary search · ⁨การค้นหาเชิงเส้นเทียบกับ binary search⁩

Binary search halves the range each step — far fewer checks. · ⁨Binary search หักครึ่งช่วงในแต่ละขั้นตอน — ตรวจสอบน้อยลงมาก.⁩

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) ให้สมบูรณ์. กลับคืน index ของ item แรกที่เท่ากับ target, หรือ -1 ถ้ามันไม่อยู่ใน array. ตรวจสอบ items จาก index 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. · ⁨คลิก Run เพื่อดูผลลัพธ์ที่นี่⁩

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) สำหรับ sorted array. ใช้ low/high bounds และตรวจสอบค่าตรงกลางในแต่ละขั้นตอน. กลับคืน index ของ 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. · ⁨คลิก Run เพื่อดูผลลัพธ์ที่นี่⁩

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 (linear scan). กลับคืน 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. · ⁨คลิก Run เพื่อดูผลลัพธ์ที่นี่⁩

Searching: linear and binary · ⁨การค้นหา: Linear และ Binary⁩

Finding a value

การหาค่าค่าหนึ่ง

Linear search

การค้นหาแบบเชิงเส้น

How fast is linear search?

Linear search เร็วแค่ไหน?

Binary search needs a sorted array

Binary search ต้องใช้ array ที่เรียงลำดับแล้ว

The binary search idea

ความคิดเรื่อง Binary search

When a value is missing

เมื่อค่าไม่พบ

Common mistakes

ข้อผิดพลาดที่พบบ่อย

Now you try

ลองดูเลย

Linear vs binary search · ⁨การค้นหาเชิงเส้นเทียบกับ binary search⁩

Handout · ⁨เอกสารประกอบการเรียน⁩

Log in or create account · ⁨เข้าสู่ระบบหรือสร้างบัญชี⁩

Your subject · ⁨วิชาของคุณ⁩

All sections · ⁨ทุกส่วน⁩

Feedback & help · ⁨ความคิดเห็น &ความช่วยเหลือ⁩