[JavaScript] 2. 탐색 알고리즘

1. 선형 탐색(Linear Search)

선형 탐색은 배열의 각 요소를 순차적으로 확인해 원하는 값을 찾는 알고리즘으로, 배열의 길이에 비례하여 시간이 소요되므로, 최악의 경우 O(n)의 시간 복잡도를 가집니다.

// 선형 탐색 알고리즘
function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) {
      return i; // 찾은 경우 인덱스를 반환
    }
  }

  return -1; // 찾지 못할 경우 -1 반환
}

// example
const numbers = [5, 2, 4, 1, 6];
const target = 6;
const index = linearSearch(numbers, target);
console.log(index); // 출력: 4

---

2. 이진 탐색(Binary Search)

이진 탐색은 정렬된 배열에서 중간 요소와 비교하여 원하는 값을 찾는 알고리즘으로, 배열을 반으로 나누어 탐색 범위를 줄여가므로, O(log n)의 시간 복잡도를 가집니다. 이진 탐색을 사용하기 위해 배열이 반드시 정렬되어야 합니다.

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    if (arr[mid] === target) {
      return mid; // 찾을 경우 index 반환
    } else if (arr[mid] < target) {
      left = mid + 1; // 오른쪽 절반 탐색
    } else {
      right = mid - 1; // 왼쪽 절반 탐색
    }
  }
  return -1; // 찾지 못할 경우 -1 반환
}

// example
const sortedNumbers = [1, 2, 3, 5, 8];
const target2 = 5;
const index2 = binarySearch(sortedNumbers, target2);
console.log(index2);

---

 

GitHub - Koras02/javascript-algorithm