이진 탐색 (Binary Search)

이진 탐색 (Binary Search) 설명:

이진 탐색은 정렬된 배열에서 원하는 값을 효율적으로 찾기 위한 알고리즘입니다. 선형 탐색에서는 배열의 모든 요소를 하나씩 확인하며 원하는 값을 찾지만, 이진 탐색은 배열을 절반씩 나누면서 원하는 값의 위치를 찾아냅니다. 이 때문에 시간 복잡도는 O(log n)이 됩니다.

작동 원리:
1. 배열의 중간 위치에 있는 값을 확인합니다.
2. 중간 위치의 값이 원하는 값과 동일하면 그 위치를 반환합니다.
3. 원하는 값이 중간 위치의 값보다 작으면 중간을 기준으로 왼쪽 부분 배열에서 탐색을 계속합니다.
4. 원하는 값이 중간 위치의 값보다 크면 중간을 기준으로 오른쪽 부분 배열에서 탐색을 계속합니다.
5. 배열의 크기가 1이 될 때까지 위의 과정을 반복합니다.

대표 예제:

1. 기본 이진 탐색:

function binarySearch(array, target) {
  let low = 0;
  let high = array.length - 1;

  while (low <= high) {
    let mid = Math.floor((low + high) / 2);

    if (array[mid] === target) {
      return mid; // target의 인덱스 반환
    } else if (array[mid] < target) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }

  return -1; // target을 찾지 못한 경우
}

2. 재귀를 사용한 이진 탐색:

function binarySearchRecursive(array, target, low, high) {
  if (low > high) return -1;

  let mid = Math.floor((low + high) / 2);
  
  if (array[mid] === target) {
    return mid;
  } else if (array[mid] < target) {
    return binarySearchRecursive(array, target, mid + 1, high);
  } else {
    return binarySearchRecursive(array, target, low, mid - 1);
  }
}

3. 이진 탐색을 사용하여 "sqrt(x)" 구하기 (x의 제곱근을 정수로 반환):

function sqrt(x) {
  if (x < 2) return x;

  let low = 1;
  let high = x;

  while (low <= high) {
    let mid = Math.floor((low + high) / 2);
    let num = mid * mid;

    if (num === x) {
      return mid;
    } else if (num < x) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }

  return high;
}

4. 정렬된 2D 행렬에서 값 찾기:

// 해당 예제는 간략화 되었습니다.
function searchMatrix(matrix, target) {
  let row = 0;
  let col = matrix[0].length - 1;

  while (row < matrix.length && col >= 0) {
    if (matrix[row][col] === target) {
      return true;
    } else if (matrix[row][col] < target) {
      row++;
    } else {
      col--;
    }
  }

  return false;
}

5. 첫 번째와 마지막 위치 찾기:
   정렬된 배열에서 주어진 target 값의 시작 위치와 종료 위치를 찾는 문제입니다.

function searchRange(nums, target) {
    function findLeft(nums, target) {
        let idx = -1;
        let low = 0;
        let high = nums.length - 1;
        while (low <= high) {
            let mid = Math.floor((low + high) / 2);
            if (nums[mid] === target) idx = mid;
            if (nums[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return idx;
    }
    
    function findRight(nums, target) {
        let idx = -1;
        let low = 0;
        let high = nums.length - 1;
        while (low <= high) {
            let mid = Math.floor((low + high) / 2);
            if (nums[mid] === target) idx = mid;
            if (nums[mid] <= target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return idx;
    }

    return [findLeft(nums, target), findRight(nums, target)];
}

위의 예제들은 이진 탐색의 다양한 응용을 보여줍니다. 이진 탐색은 정렬된 데이터에서 효율적인 탐색을 가능하게 해주므로, 다양한 문제에 응용될 수 있습니다.