STUDY/Algorithm

탐색 알고리즘 (Search Algorithm) / 선형 탐색, 이진 탐색

ez1n 2023. 4. 2. 20:30

 

[탐색 알고리즘]

 


 

<STUDY>

 

선형 탐색 (Linear Searching)

특정 값이 배열 안에 포함되어 있는지 순서대로 살펴보는 방법
  • Big O : O(n)
  • indexOf Includes find findIndex 메소드

 

 

💡 배열 안의 target 위치를 반환하는 함수 (값이 없는 경우 -1 반환)

function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (target === arr[i]) return i;
  }
  return -1;
}

 

Big O

  • Best : O(1)
  • Average : O(n)
  • Worst : O(n)

 


 

이진 탐색 (Binary Search)

범위를 정해서 그 안에서만 탐색하는 방법
  • 데이터가 정렬되어 있어야 함
  • 분할 정복 (dividing and conquering)

 

 

💡 분류된 배열을 인자로 받아 target의 위치를 반환하는 이진 탐색 함수 (값이 없는 경우 -1 반환)

function binarySearch(arr, target){
    let left = 0;
    let right = arr.length - 1;
    
    while(right >= left) {
        const mid = Math.floor((left + right) / 2);
        
        if (arr[mid] === target) return mid;
        if (arr[mid] > target) right = mid - 1; 
        if (arr[mid] < target) left = mid + 1;
    }
    
    return -1;
}

 

Big O

  • Best : O(1)
  • Average : O(log n)
  • Worst : O(log n)

 

 


 

알고리즘 공부가 필요하다고 생각해서 기초부터 다시 시작하고 있는데

구현하는 것에만 초점을 맞춰서 문제를 풀고 있었던 것 같다.

 

어떤 알고리즘을 선택하는 것이 효율적인지 생각해야 하는데 결과 자체에만 신경을 쓰고 있었기 때문에

그동안 실력이 늘지 않았던 것이 아닐까 하는 생각이 들었다.

 

앞으로는 어떤 알고리즘을 사용해야 더 효율적으로 구현할 수 있을지에 대해서 더 많이 생각하고 풀어야겠다.

 

결과보다 과정을 중요시할 수 있도록 열심히 해야징!