[알고리즘] 정렬된 연결 리스트에서 이진 탐색 사용하기(C언어)

728x90

이진 탐색의 한계점을 공부하던 와중에 동적인 자료구조에서는 사용이 힘들 수 있다는 것을 알았다. 하지만 최근에 스택과 큐를 C로 구현해봤기 때문에 큐를 이용해서 이진 탐색 함수를 만들어보면 재밌을 것 같아서 시도해 보았다. 

 

구상

일반적인 이진 탐색은 배열에서 진행 되기 때문에 값에 접근함에 있어서 배열과 연결 리스트가 어떤 차이점을 가지고 있는지 먼저 생각해 보자. 큐를 사용할 것이기 때문에 사용할 큐에 대한 소스코드는 더보기에 첨부하겠다.

#include <stdio.h>
#include <stdlib.h>
typedef struct Node{
    int data;
    struct Node* next;
} Node;

typedef struct Queue{
    Node* front;
    Node* rear;
    int count;
} Queue;

void initQueue(Queue* queue){
    queue -> front = queue -> rear = NULL;
    queue -> count = 0;
}

int isEmpty(Queue* queue){
    return queue -> count == 0;
}

void enqueue(Queue* queue, int data){
    Node *newnode=(Node*)malloc(sizeof(Node));
    newnode -> data = data;
    newnode -> next = NULL;
    if(isEmpty(queue)){
        queue -> front = newnode;
    }
    else{
        queue -> rear -> next = newnode;
    }
    queue -> rear = newnode;
    queue -> count++;
}

int dequeue(Queue* queue){
    int data;
    Node* ptr;
    if(isEmpty(queue)){
        printf("Error : Queue is empty!!\n");
        return 0;
    }
    ptr=queue->front;
    data=ptr->data;
    queue->front=ptr->next;
    free(ptr);
    queue->count--;
    return data;
}

void printQueueContents(Queue* queue) {
    if (isEmpty(queue)) {
        printf("Queue is empty.\n");
        return;
    }

    Node* currentnode = queue->front;

    printf("Queue Contents: ");
    while (currentnode != NULL) {
        printf("%d ", currentnode->data);
        currentnode = currentnode->next;
    }
    printf("\n");
}

배열	연결 리스트
인덱스를 이용해서 어디서든 값에 접근할 수 있음	next, front, rear 를 이용해서만 다른 값으로 이동할 수 있음

이진 탐색을 하기 위해서는 첫 번째 자료가 오름차순 또는 내림차순이어야 하고 두 번째 시작과 끝이 존재할 때 가운데 인덱스(또는 포인터)로 접근할 수 있어야 한다. 배열은 인덱스를 통해서 그냥 접근하면 그만이었지만 연결 리스트는 문제가 있다. 그것은 바로 무작위 지점으로 접근하지 못한다는 점이다. 연결 리스트는 반드시 front나 rear를 통해서 양 끝으로 점프하거나 next포인터를 통해서만 한 칸씩밖에 이동하지 못한다. 연결 리스트로 대입된 값들은 오름차순이라고 가정하고 문제를 해결해 보자.

 

중간 포인터 찾기(투 포인터) 

 

일단 투 포인터의 로직은 아래와 같다.

먼저 포인터 두 개를 사용해서 시작 점을 동시에 가리키게 한다. 파란색 포인터를 left(느린) 포인터, 빨간색 포인터를 right(빠른) 포인터라고 하자.

 

left는 한 칸씩 이동하고 right는 두 칸 씩 이동할 것이다. 시작 포인터를 start_pointer, 도착 포인터를 end_pointer이라고 하자. right가 left의 두 배만큼 이동하기 때문에 right가 end_pointer에 도달하면 left는 주어진 구간(start_pointer ~ end_pointer)의 중간에 위치하게 될 것이다. 

 

1회 실행

2회 실행

3회 실행

4회 실행

4.5회 실행

Node* find_middle(Queue* queue, Node *start_pointer, Node *end_pointer){
    struct Node* left=start_pointer;
    struct Node* right=start_pointer;
    while(1){
    	// 시작부터 right(초기 값은 start_pointer)와 end_pointer가 같으면 start_pointer 반환
        if(right==end_pointer) return start_pointer;
        else if(right!=end_pointer){ // right 한 칸 이동
            right=right->next;
        }
        if(right==end_pointer) return left; // 끝에 도달 했는지 확인
        if(right!=end_pointer){ // right 다시 한 칸 이동, left 한 칸 이동
            right=right->next;
            left=left->next;
        }
    }
}

검사 범위 안에 있는 요소의 개수가 짝수개이면 정확한 가운데를 찾지 못하기 때문에 내림을 선택해서 한 칸 앞에 있는 원소를 선택하는 기존 이진 탐색 방식의 특성을 살렸다.

 

원소의 존재성 찾기

 

이진 탐색의 목적은 두 가지로 나눌 수 있다. 자료 구조에 원소가 존재하는지, 아니면 원소의 위치가 어디인지이다. 하지만 연결 리스트에서 원소의 위치를 알아내는 것은 인덱스가 정의되어 있는 자료 구조에서만 유효성이 있는 것으로 생각되어 만들지 않았다.

// 오름차순으로 입력 된 큐라고 가정할 때
int binary_search_existence(Queue* queue, Node *start_pointer, Node *end_pointer, int target){
    struct Node* left=start_pointer;
    struct Node* right=end_pointer;
    while(1){
        struct Node* mid= find_middle(queue, left, right);
        if(left==right && target!=mid->data) return 0;
        if(target==mid->data)return 1;
        else if(target>mid->data) left=mid->next;
        else if(target<mid->data) right=mid;
    }
}