3. 검색

👀  검색?

1. 자료를 얻기 위해 자료 구조의 항목들을 반복적으로 접근하는 것

2. 배열이 정렬되었는지 여부에 따라 선형 검색과 이진 검색을 할 수 있다.

 

🟣 선형 검색

1. 배열의 각 항목을 한 인덱스씩 순차적으로 접근하면서 동작.

2. 정렬되어 있지 않은 배열에도 사용 가능하기 때문에 유연하다.

3. 하지만 최악의 경우 배열의 모든 항목을 확인해야 되기 때문에 시간 복잡도가 이진 검색에 비해 높다.

function linearSearch(array,n){
    for(var i=0; i<array.length; i++){
        if(array[i]==n){
            return true;
        }
    }
    return false;
}
console.log(linearSearch([1,2,3,4,5,6,7,8,9],6)); //true
console.log(linearSearch([1,2,3,4,5,6,7,8,9],10)); //false

n이 6이면 for문 안쪽은 6번 반복한다.

n이 10이면 for문 안쪽은 9번 반복 후 if문의 조건이 충족되지 않기 때문에 for문을 빠져나와 false를 return 하게 된다.

그래서 n만큼 항목을 반복 접근해야 하기때문에 시간복잡도는 O(n)이다.

 

🟣 이진 검색

1. 배열의 중간값을 확인해 원하는 값보다 작으면 알고리즘은 중간 값보다 작은 쪽을 검색하고

    원하는 값보다 크면 알고리즘은 중간 값보다 큰 쪽을 검색한다.

2. 그래서 정렬되어 있는 배열에만 사용 가능하다.

3. 최악의 경우에도 선형 검색보다 확인해야 하는 항목이 최대 반이나 줄어들기 때문에 시간 복잡도가 선형 검색보다 낮다.

function binarySearch(array,n){
    var lowIndex = 0; highIndex = array1.length-1;
    
    while(lowIndex<=highIndex){
        var minIndex = Math.floor((highIndex+lowIndex)/2);
        if(array[midIndex]==n){
            return midIndex;
        }
        else if(n>array[midIndex]){
            lowIndex = midIndex+1;
        }
        else{
            highIndex = midIndex-1;
        }
    }
    return -1;
}

console.log(binarySearch([1,2,3,4],4)//3
console.log(binarySearch([1,2,3,4],5)//-1

lowIndex보다 highIndex값이 크거나 같아질때동안 반복하는데

n이 array 배열의 중간 값보다 크면 lowIndex에 midIndex+1을 해서 minIndex 값을 키워서 다시 비교한다.

n이 array 배열의 중간 값보다 작으면 highIndex에 midIndex-1을 해서 minIndex값을 줄여서 다시 비교한다.