순차 검색(Linear Search), 이진 검색(Binary Search)

순차 검색(Linear Search)

• 일렬로 되어있는 자료를 처음부터 마지막까지 순서대로 비교하여 검색하는 방법
• 가장 간단하고 직접적인 방법

출처: GeeksforGeeks

 

순차 검색 자바 구현

public class SequentialSearch {
    public static void main(String[] args) {
        int unorderedArr[] = {26, 35, 88, 44, 34, 12, 96, 31, 64};
        int orderedArr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        SequentSearch ss = new SequentSearch();
        ss.searchUnorderedList(unorderedArr, 12);
        ss.searchOrderedList(orderedArr, 9);
    }
}

class SequentSearch {
    public void searchUnorderedList(int arr[], int key) {
        int i = 0;
        while (i < arr.length && key != arr[i]) {
            i++;
        }
        if (i < arr.length) {
            System.out.printf("검색성공! 찾은 인덱스 %d", i);
        } else {
            System.out.printf("검색실패!");
        }
        System.out.println();
    }

    public void searchOrderedList(int arr[], int key) {
        int i = 0;
        // 찾는 key값이 정렬된 배열보다 커지면 연산을 멈춘다.
        // 검색하려는 값이 없어도 배열의 모든 인덱스를 뒤져야 하는 searchUnorderedList보다 효율적 
        while (arr[i] < key) {
            i++;
        }
        if (arr[i] == key) {
            System.out.printf("검색성공! 찾은 인덱스 %d", i);
        } else {
            System.out.printf("검색실패!");
        }
        System.out.println();
    }
}

 

 

이진 검색(Binary Search)

• 가운데에 있는 항목을 키값과 비교하여 키값이 더 크면 오른쪽 부분을 검색, 더 작으면 왼쪽 부분을 검색하는 방법을 반복 수행
• 정렬된 자료 검색에서만 사용 가능

출처: GeeksforGeeks

 

 

 

 

학습 교재

자바로 배우는 쉬운 자료구조 - 이지영 지음

누구나 자료구조와 알고리즘 - 제이 웬그로우 지음