검색 (2) - 선형 검색 (Sequential Search, 배열)

1. 알고리즘 개요

• 자료집합의 데이터를 순차적으로 탐색하는 방법
• loop를 돌려서 검색 데이터를 찾으면 반환하는 방식

 

2. 연산

• 삽입 : 자료집합 맨 뒤에 삽입 : O(1)
• 삭제 : 원소를 찾아서 지우고, 뒤의 원소들을 앞으로 당김 : O(N)
• 검색 : 원소를 찾아서 반환 : O(N)

 

3. 소스코드

import java.util.Arrays;

public class ArraySeqMap {
    private Integer[] array;
    private int capacity;
    private int count;

    public ArraySeqMap(int capacity) {
        this.capacity = capacity;
        this.count = 0;
        this.array = new Integer[capacity];
    }

    public Integer get(int val) {
    // 원소를 찾아서 반환 : O(N)
    
        for (int i = 0; i < count ; i++) {
            if (array[i] == val)
                return val;
        }

        return null;
    }

    public boolean put(int val) {
    // 자료집합 맨 뒤에 삽입 : O(1)
    
    	if(count < capacity){
        	array[count] = val;
        	count++;
        	return true;
        }
        return false;
    }

    public boolean remove(int val) {
    // 원소를 찾아서 지우고, 뒤의 원소들을 앞으로 당김 : O(N)
    
        int indexToRemove = -1;
        for (int i = 0; i < count; i++) {
            if (array[i] == val) {
                indexToRemove = i;
            }
        }

        if (indexToRemove != -1) {
            for (int i = indexToRemove; i < count; i++) {
                if (i == capacity - 1) {
                    array[i] = null;
                } else {
                    array[i] = array[i + 1];
                }
            }
            count--;
            return true;
        }
        return false;
    }

    public void check() {
        System.out.println(Arrays.toString(array));
    }
}

 

4. 삭제 성능을 높히는 방법

1) Lazy Deletation : ArraySeqMap에서 삭제는 loop 두번으로 이루어지는데, 첫번째 loop는 삭제할 원소를 찾는 loop, 두번째 loop는 원소들을 앞으로 당기는 loop이다. Lazy Deletation은 삭제시 두번째 loop에서 원소들을 앞으로 당기지 않고 입력될 가능성이 없는 데이터로 대체해놓는 것이다. 나중에 데이터가 입력될때 뒤에서부터 입력하는 것이 아니라, 해당 대체된 자리에 차곡차곡 입력한다.

 

 

5. Reference