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

한국어

값 찾기

일반적인 작업은 검색입니다: 배열에 특정 값이 있는지, 있다면 어디에 있는지 확인하는 것입니다.
일반적으로 찾은 위치의 인덱스를 반환하거나, 없으면 **-1**를 반환합니다.
두 가지 방법을 배웁니다: 선형 검색(임의의 배열에서 작동)과 이진 검색(정렬된 배열이 필요하며 훨씬 빠름).

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번 확인합니다. 이를 선형 시간이라고 합니다.
작은 배열에는 전혀 문제가 없습니다. 그러나 매우 큰 정렬된 배열에서는 더 나은 방법이 있습니다.

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 내부에 작성하거나 제시된 메서드를 완성하십시오.
Run 버튼을 눌러 컴파일하고 실행한 후, Answer 확인 버튼을 누르세요.
코드는 서버에서 컴파일되고 실행되므로 첫 실행에서도 빠릅니다.

Explore · ⁨탐색하기⁩

Linear vs binary search · ⁨선형 검색 대 이진 검색⁩

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 · ⁨선형 검색 대 이진 검색⁩

Handout · ⁨교재 자료⁩

Log in or create account · ⁨로그인 또는 계정 만들기⁩

Your subject · ⁨현재 과목⁩

All sections · ⁨모든 섹션⁩

Feedback & help · ⁨피드백 및 도움말⁩