선형탐색

www.geeksforgeeks.org/linear-search

정의

💡 한쪽 끝에서 시작하여 원하는 요소를 찾을 때까지 목록의 각 요소를 조사하는 알고리즘

요소를 찾지 못하는 경우에는 데이터셋의 끝까지 간다.

효용

• 배열, 연결리스트의 정렬여부와 무관하게 원소를 탐색할 수 있음
• 그러나 배열이 정렬되어 있고 원소가 배열 내에 존재하는 경우에 탐색 성능이 올라감

절차

• 1. 시작: 컬렉션의 첫번째 원소에서부터 시작
• 2. 비교: 현재의 원소와 찾고자하는 원소와 비교
• 3. 확인: 현재 원소가 찾고자하는 원소인 경우 true 또는 현재 원소의 인덱스를 반환
• 4. 이동: 찾고자 하는 원소가 아닌 경우에는 컬렉션의 다음 원소로 이동
• 5. 반복: 컬렉션의 끝에 도달할 때까지 2에서 4의 과정을 반복
• 6. 찾지 못한 경우: 컬렉션의 끝에 도달해도 원소를 찾을 수 없는 경우에는 찾을 수 없음 반환

구현

Horwitz 교재

int SequentialSearch(int *arr, int n, int x) {
	int i = 0; // 탐색 시작 지점
	for(;i < n && arr[i] != x; i++); // 탐색범위: 배열의 끝까지
	if(i == n) return -1; // 배열의 끝에 도달한 경우에 -1 반환
	else return i; // 원소를 찾은 경우 원소의 인덱스 반환
}

내 답안

int SequentialSearch(int *arr, int n, int x) {
    for (int i = 0; i < n; i++) { // NOTE: 초기화식을 밖으로 뺄 것
        if (arr[i] == x) // NOTE: 조건을 반복문의 조건식에 포함시킬 것
            return i;
    }
	return -1;
}

피드백

• 반복문에 쓰이는 인덱스 자체를 반환하고자 하는 경우 초기화를 반복문 밖에서 할 수 있다.
• 조건식에 인덱스 비교 연산 뿐만 아니라 다른 조건도 추가할 수 있다.
• 선형탐색 시 원소를 찾은 경우, 프로그램의 성능을 위해 탐색을 중단하는 로직도 넣을 것