선형검색과 이진검색

(단어) 정렬 : 항목들을 체계적으로 정리하는 과정, 배열 : 한 자료형의 여러 값들이 메모리 상에 모여있는 구조

선형 : 선의,일자의, 이진: 둘의,두 부분,두 조각

선형검색

개념

데이터가 모인 집합의 처음부터 끝까지 하나씩 순서대로 비교하는 검색 ,즉 순차적으로 검색한다.

 

특징

- O(N)
- 쉬움
- 비효율적
- 정렬되지 않아도 사용가능

데이터양이 많아질수록 검색 소요 시간도 그만큼 비례한다.

 

코드

int LinearSerach(int arr[],int size,int target) //매개변수
{
	for(int i=0;i<size;i++){
    	if(arr[i] == target){ // 비교
        	return i; //찾았음으로 리턴
		}
    }
	return -1; // 찾지 못함
}

꾸준함

이진검색

개념

반으로 나누어 연산하는 것, 즉 중간값부터 탐색을 한다.

 

특징

- O(log N)
- 연산 처리 속도 매우 빠름
- 반드시 정렬되어 있어야 함

70억명중 한명을 찾으려면 최대 몇번 검색을 해야할까? 이진검색에서는 단 33번만하면 찾을 수 있다.

대단하지 않은가? 선형검색으로 찾으려면.... 살려주세요

 

코드

int BinarySearch(int arr[],int size,int target){
    int first = 0;
    int last = size-1; //배열의 크기가 10이면 0 때문에 -1을 해줘야 함
    int mid;
    while(first <= last){
        mid = (first+last) / 2;
        if(target == arr[mid]){
            return mid;
        }
        else if(target < arr[mid]){ // 왼쪽이동
            last = mid-1;
        }
        else{
            first = mid + 1; // 오른쪽 이동
        }
    }
    return -1;
}

항상 초심을 잃지 말자