선형 탐색 (Linear Search)

  1. 개념 설명: 선형 탐색은 배열의 처음부터 끝까지 순차적으로 탐색하는 가장 기본적인 탐색 알고리즘입니다. 정렬되지 않은 배열에서도 사용할 수 있는 장점이 있습니다.

  2. 처리 과정 순서:

  1. 배열의 첫 번째 원소부터 시작
  2. 현재 원소가 찾고자 하는 값인지 확인
  3. 찾았다면 해당 인덱스 반환
  4. 찾지 못했다면 다음 원소로 이동
  5. 배열 끝까지 찾지 못하면 -1 반환
  1. 코드 예
# Python
def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i  # 찾은 원소의 인덱스 반환
    return -1  # 원소를 찾지 못한 경우

// C
int linearSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target)
            return i;
    }
    return -1;
}

// Java
public class LinearSearch {
    public static int linearSearch(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target)
                return i;
        }
        return -1;
    }
}
  1. 주의사항:

이진 탐색 (Binary Search)

  1. 개념 설명: 이진 탐색은 정렬된 배열에서 중간값을 기준으로 탐색 범위를 절반씩 줄여가며 찾는 알고리즘입니다. 매우 효율적인 탐색 방법이지만, 배열이 정렬되어 있어야 합니다.

  2. 처리 과정 순서:

  1. 배열의 중간 원소를 선택
  2. 중간 원소와 찾고자 하는 값을 비교
  3. 찾고자 하는 값이 중간 원소보다 작으면 왼쪽 부분 배열에서 탐색
  4. 찾고자 하는 값이 중간 원소보다 크면 오른쪽 부분 배열에서 탐색
  5. 찾을 때까지 1-4 과정을 반복
  1. 코드 예

# Python
def binary_search(arr, target):
    left = 0
    right = len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1

# 재귀적 구현
def binary_search_recursive(arr, target, left, right):
    if left > right:
        return -1
        
    mid = (left + right) // 2
    
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, right)
    else:
        return binary_search_recursive(arr, target, left, mid - 1)

// C
int binarySearch(int arr[], int left, int right, int target) {
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target)
            return mid;
        
        if (arr[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return -1;
}

// Java
public class BinarySearch {
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (arr[mid] == target)
                return mid;
                
            if (arr[mid] < target)
                left = mid + 1;
            else
                right = mid - 1;
        }
        return -1;
    }
}
  1. 주의사항: