순차탐색

순차탐색은 탐색하여야 할 자료들을 처음부터 마지막까지 순차적으로 비교하면서 원하는 자료를 찾는 방식입니다.

순차 탐색은 하나하나 비교하며 내가 원하는 값이 어디있는지 확인하는 방식이기 때문에 자료가 정렬되어 있지 않아도 탐색이 가능합니다.

배열을 처음부터 끝까지 전부 탐색하였는데 원하는 값이 없다면 탐색 실패입니다.

C 언어 코드

#include <stdio.h>

int main() {
	int n; // 자료를 몇개 입력받을지
	scanf("%d", &n);
	
	int arr[n]; // n 개의 자료를 배열에 저장
	for (int i = 0 ; i != n ; i++){
		scanf("%d", &arr[i]);
	}
	
	int want; // 찾고싶은 값을 입력받음
	scanf("%d", &want);
	
	for (int i = 0 ; i != n ; i++){
    	// 배열을 순차탐색하며 내가 원하는 값과 같은 값이
        // 나오면 그 값이 몇번째인지 출력하고 코드를 끝낸다.
		if (arr[i] == want){
			printf("%d", i + 1);
			return 0;
		}
        
        // 배열의 마지막 값까지 확인했는데도
        // 내가 원하는 값과 같은 값이 없다면 실패를 출력한다.
		else if (i == n - 1){
			printf("실패");
		}
		
	}
	
	return 0;
}

BigO 표기법 시간 복잡도 O(n)

이진탐색

이진탐색이란 정렬돼 있는 데이터에서 특정한 값을 찾아내는 알고리즘입니다.

이진탐색은 이분탐색이라고도 불립니다.

이진탐색은 탐색 범위를 반으로 나누어 찾는 값을 포함하는 범위를 좁혀가는 방식으로 동작합니다.

배열에서의 동작방식
1. 정렬된 배열에서 중간 인덱스(mid) 찾기
2. 찾으려는 값(target)과 중간 값(mid_val) 비교하기
3. target이 mid_val보다 작으면 mid를 기준으로 왼쪽 부분 배열 탐색하기
4. target이 mid_val보다 크면 mid를 기준으로 오른쪽 부분 배열 탐색하기
5. 탐색 범위를 반으로 줄이기
6. 탐색 범위가 더 이상 없을 때까지 위 과정을 반복하기

BigO 표기법 시간 복잡도 O(log n)