순차탐색, 이진탐색

순차탐색(Sequentail Search)

  순차탐색은 특정한 원소를 찾기 위해 원소를 순차적으로 하나씩 탐색하는 방법이다.

  아래의 배열에서 '배열'이라는 문자열을 찾는다고 하면

인덱스	0	1	2	3	4
원소	순차	탐색	정렬	배열	리스트

  앞에서부터 문자열을 순차적으로 탐색해서 찾은 문자열의 인덱스를 반환한다.

 

예제코드

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define LENGTH 100

char **array;
int founded;

int main(void){
  int n;
  char *word;
  word = malloc(sizeof(char) * LENGTH);
  scanf("%d %s", &n, word);
  array = (char**)malloc(sizeof(char*) * n);
  
  for(int i = 0; i < n; i++){
    array[i] = malloc(sizeof(char*) * n);
    scanf("%s", array[i]);
  }
  
  for(int i = 0; i < n; i++){
    if(!strcmp(array[i], word)){
      printf("%d번째 원소입니다.", i + 1);
      founded = 1;
    }
  }
  
  if(!founded) printf("원소를 찾을 수 없습니다.\n");
  system("pause");
  return 0;
}

  5 배열

  순차 탐색 정렬 배열 리스트

  이렇게 입력하면 '4번째 원소입니다' 라는 결과값이 출력된다.

 

  n은 배열의 크기, word는 문자열이다.

  첫번째 반복문으로 배열의 원소값을 입력하고 두번째 반복문에서 값을 찾는다.

  word를 기준으로 배열의 인덱스를 하나씩 증가시키며 찾아나가고 strcmp함수로 인덱스의 원소값, 그리고 찾고자하는

  문자열인 word를 비교해서 같다면 해당 인덱스값 + 1을 해서 출력을 해준다.

  +1을 한 값으로 출력하는것은 인덱스 번호는 0부터 시작하기 때문에 몇번째에 있는지 출력하기 위해 더했다.

 

  순차탐색은 데이터 정렬 유무에 상관없이 가장 앞에 있는 원소부터 하나씩 확인해야 한다는 점에서 O(N)의

  시간 복잡도를 갖는다.

 

이진탐색(Binary Search)

  이진탐색은 배열 내부 데이터가 이미 정렬되어 있는 상황에서만 사용가능한 알고리즘이다.

  탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 특징이 있다.

 

  이진 탐색의 탐색과정은 다음과 같다.

  찾을 원소값이 37이고

인덱스	0	1	2	3	4	5	6	7	8
원소	15	27	37	46	57	69	73	85	98

  탐색할 배열이 이렇게 정렬되어 있을 때 중앙의 인덱스 원소값을 기준으로 먼저 탐색한다.

  그럼 가운데 인덱스는 4고 원소값은 57인데 찾을 원소보다 크기 때문에 왼쪽으로 탐색을 하게 된다.

인덱스	0	1	2	3	4	5	6	7	8
원소	15	27	37	46	57	69	73	85	98

  왼쪽에 남은 인덱스인 0 1 2 3 중에서 중간값인 27을 기준으로 한번 더 체크하면 27이 더 작기 때문에

  오른쪽으로 탐색하고 바로 오른쪽 인덱스인 2번인덱스를 탐색하여 체크한다.

  

  이렇게 모든 인덱스를 탐색하지 않아도 되기 때문에 순차탐색보다 더 빠르게 찾을 수 있다.

  

  이진 탐색은 한번 확인할 때마다 봐야하는 원소의 개수가 절반씩 줄어든다는 점에서 탐색시간이 O(logN)의

  시간 복잡도를 갖는다.

 

  start, mid, end로 정의해서 mid위치에 있는 원소와 반복적으로 비교하게 된다.

 

예제코드

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define MAX_SIZE 100000

int a[MAX_SIZE];
int founded = 0;

int search(int start, int end, int target){
  if(start > end) return -9999;
  
  int mid = (start + end) / 2;
  
  if(a[mid] == target) return mid;//mid값과 target값이 일치한다면 mid값을 반환
  else if(a[mid] > target) return search(start, mid - 1, target);//mid값이 target보다 크다면
  else return search(mid + 1, end, target);//mid값이 target보다 작다면
}

int main(void){
  int n, target;
  scanf("%d %d", &n, &target);
  
  for(int i = 0; i < n; i++) scanf("%d", &a[i]);
  
  int result = search(0, n - 1, target);
  
  if(result != -9999) printf("%d번째 원소입니다.\n", result + 1);
  else printf("원소를 찾을 수 없습니다.\n");
  
  system("pause");
  return 0;
}

  n은 배열의 크기 target은 찾고자하는 값이다.

  첫 반복문에서 배열의 원소값들을 입력해주는데 이때 원소값들은 정렬된 상태로 입력해줘야 한다.

  result는 search함수에서 처리하고 난 반환값이다.

  첫 시작은 0번인덱스가 되어야 하고 마지막 인덱스는 배열 크기 - 1이고 찾는 값을 입력한 값을 넘겨준다.

 

  search에서는 제일먼저 start와 end를 비교해서 start가 더 크다면 -9999를 반환하도록 한다.

  처음부터 이 조건문에 걸릴일은 없겠지만 처리과정을 반복하면서 찾고자하는 값이 배열에 없으면 더 진행하지않고

  반환하기 위해서 맨 위에 작성한다.

 

  mid는 가운데 인덱스 값을 찾기 위해 start와 end를 더한 값을 2로 나눠준다.

 

  a배열의 가운데 인덱스인 mid번째 인덱스의 원소값이 찾고자하는 값인 target과 같다면 더 처리할 필요가 없으므로

  인덱스 값인 mid를 반환한다.

 

  a[mid]가 target보다 크다면 왼쪽에서 탐색해야 하므로 search함수로 값을 다시 넘긴다.

  start는 그대로 0이어야 하니까 start로, end는 mid보다 하나 작은 인덱스까지만 탐색해야 하니까 mid - 1을 해준다.

 

  a[mid]가 target보다 작다면 오른쪽에서 탐색해야 하므로 start는 mid보다 하나 더 큰 값으로, end는 그대로 end를 

  넘겨 처리한다.

 

  출력은 result가 원소값이 없을때의 반환값인 -9999가 아니라면 몇번째 원소인지 출력해준다.

  이때 result + 1을 해준 이유는 배열은 0부터 시작하니까 1부터 시작하도록 만들어서 출력하기 위해서다.

  

 

레퍼런스

패스트캠퍼스 올인원 패키지 - 소프트웨어 베이직