[알고리즘] 검색 알고리즘- 선형 검색, 이진 검색 _JAVA(자바)

 

 

선형알고리즘과 이진 검색 알고리즘

 

 

들어가며

데이터를 조회할때 검색 알고리즘을 사용하곤 합니다. 그래서 이번 포스팅에서는 가장 검색의 기본적인 알고리즘인

선형 검색과 이진검색 알고리즘에 대해서 알아보도록 하겠습니다. 

 

---

 

선형 검색

선형검색이란?

리스트나 배열에서 순차적으로 배열 요소를 검사해 나가며 원하는 값을 찾는 방법입니다. 즉 배열[0]부터 배열[N]까지의 요소 중 원하는 KEY값을 찾는다고 할 수 있습니다.

 

예를 들어 {1,2,3,7,9} 값이 들어있는 배열을 생각해 봅시다.

만약 "7"이라는 값을 찾으려면 다음과 같이 arr [0]부터 arr [3]까지 찾게 됩니다.

만약에 "10"이라는 값을 찾는다고 가정하면 

다음과 같이 arr[0]~arr[4]까지 모든 배열을 검색하고 난 뒤에 종료를 하게 됩니다.

 

그럼 모든 배열을 조회하고 선형검색 알고리즘이 종료가 되기 때문에 시간복잡도는 O(n)입니다.

여기서 n은 배열이 아니라 배열 요소의 수를 말합니다.

 

선형 검색 코드

위에 예시를 코드로 작성해 보겠습니다.(메서드로 작성하겠습니다. 기본적인 자바를 배원다는 전재하로 작성하겠습니다.)

 static int 선형알고리즘(int[] arr, int n, int key){
        for (int i =0;i<n;i++){
            if (arr[i]==key)
                return i;
        }
        return -1;
    }

for문을 보면 0부터 우리가 작성한 배열의 수 n까지 반복하며 arr 배열에 찾는 키값이 있을 때만 i의 값을 반환하도록 하며

찾는 값이 없을 때는 -1로 반환합니다.

 

현재 선형검색에서는 종료조건이 두 개일 때만 작동합니다.

① if문이 통과할 때
② for문을 모두 동작했을대

 

하지만 보초법을 사용하면 해당비용을 50% 줄여 작동할 수 있습니다.

다음과 같이 int[] arr = new int[n+1] 과같이 입력한 값에서 +1을 하여 보초배열을 추가로 만들어 보초값에
찾는 key값을 넣어 하나의 종료조건을 만듭니다.

static int 선형보초법알고리즘(int[] arr, int n, int key) {
    int i = 0;
    
    arr[n] = key; // 배열의 끝에 보초(key)를 추가

    while (true) {
        if (arr[i] == key)
            break; // 찾고자 하는 값이 발견되면 반복문을 종료
        i++;
    }

    return n == i ? -1 : i; // 만약 배열의 끝에 보초가 있어서 찾고자 하는 값이 발견되지 않았을 경우 -1 반환, 아니면 해당 값의 인덱스 반환
}

보초법을 사용해 알고리즘을 구성하면 종료조건은

① if(arr [i] ==key) 일 때만 동작해 일반보다 50% 성능이 증가합니다.

---

 

이진 검색

이진 검색이란?

정렬된 리스트나 배열에서 특정한 값을 찾는 데 사용되는 알고리즘입니다. 중간값을 이용해 원하는 값을 찾는 방법입니다.

 

다음과 같이 배열에 오름차순으로 정렬된 {1,5,8,9,15,20,22,25,26} arr 배열이 있다고 가정해 봅시다. 찾고자 하는 값이 5일 때 다음과 순서로 8을 찾습니다.

시작값, 중간값, 끝값을 정해 찾고자 하는 값이 큰지 작은지 판단후에 다시 시작값,중간값,끝값을 정하며 마지막까지 이동합니다. 그리고 두개의 수만 리스트만 남는다면 첫번째 리스트가 중간값과 시작값을 가지게되며 끝값까지 비교하여 찾고자하는 5값을 찾을수있습니다! 
만약 찾고자하는 값이 리스트에 없다면 다음과같이  모든 필드값을 검색후 종료합니다. 

이진 검색 코드

static int 이진검색(int[] arr, int n, int key) {
    int 시작값 = 0;
    int 끝값 = n - 1;

    do {
        int 중간값 = (시작값 + 끝값) / 2;
        if (arr[중간값] == key)
            return 중간값;
        else if (arr[중간값] < key) {
            시작값 = 중간값 + 1;
        } else {
            끝값 = 중간값 - 1;
        }
    } while (시작값 <= 끝값); // 시작값이 끝값을 넘어가지 않을 때까지 반복

    return -1; // 값이 없을시 -1 반환
}

다음 과같이 코드를 작성해 주면 된다. 이진검색의 이진 검색의 시간 복잡도는 O(log n)입니다. n의 배열의 수를 말합니다. 

---

 

정리

이번 포스팅에서는 검색 알고리즘의 기본인 선형 검색 알고리즘과 이진 검색 알고리즘에 대해 살펴보았습니다. 선형 검색 알고리즘은 구현하기는 쉽지만 시간 복잡도가 O(n)이므로 데이터 양이 많을 경우 성능이 좋지 않습니다.

반면에 이진 검색 알고리즘은 시간 복잡도가 O(log n)이므로 선형 검색보다 훨씬 효율적입니다. 이진 검색은 배열이 정렬되어 있어야 하지만, 정렬된 상태에서는 빠른 검색을 제공하므로 많은 데이터를 효율적으로 처리할 수 있습니다.

따라서 이진 검색 알고리즘이 선형 검색 알고리즘보다 성능이 우수하며, 대부분의 상황에서 선호되는 검색 방법이라고 말할 수 있습니다

 

---

출처

• Do It 자료구조/알고리즘.