이진 탐색, Binary Search

침대위의 양갱

입력 : 정렬된 원소 리스트

출력 : 입력받은 원소 리스트에서 찾는 값이 없으면 null을 반환, 찾으면 리스트에서 인덱스(위치)를 반환.

빅오 표기법 : O(log n)

 

#javascript 

//정렬된 배열
var list=[1,2,3,4,5,7,10,33,57];
//찾고자 하는 값
var search = 33;

function binarySearch(list , find)
{   
    var start = 0;
    var end = list.length-1;
    var cnt = 1;
    var mid =-1;
    while(1)
    {
    	//그냥 나누기 2를 했더니 소수점 값이 출력되어서 idx계산이 안되더라. 
        //강제로 형변환.
        mid = parseInt((start+end)/2);
        //해당 배열의 가장 중간값을 선택.
        var sel = list[mid];
        console.log("[" + cnt + "] start : " + start + ", end : " + end + ", mid : " + mid + ", sel : " + sel);
        
        //얼씨구나. 검색하자마자 걸리면 기분 째질듯. 
        if( find == sel )
        {
            console.log(cnt + " times!");
            break;
        }
        //찾아야하는 값보다 중간값이 작으면 start를 한칸 증가.
        else if(sel < find)
        {
            start = mid+1;
        }
        //찾아야하는 값보다 중간값이 크면 end를 한칸 감소. 
        else{
            end = mid-1;
        }
        cnt++;
    }
    
}

binarySearch(list, search);

 

알고리즘을 공부할 수록 느끼는 건.

입력값이 작을 땐, 그 효용가치에 대해서 실감하기 어렵다는 것이다. 

하지만 입력값이 몇만 단위가 넘어가게 되면 정렬과 탐색에 있어서 어떤 알고리즘을 선택하느냐에 따라 시스템의 퍼포먼스가 확연히 달라진다는 것.