# 탐색 알고리즘

탐색 알고리즘이란 방대한 데이터에서 목적에 맞는 데이터를 찾아내기 위한 알고리즘을 의미한다.

탐색 알고리즘은 다양한 종류가 있지만, 대표적으로 선형 탐색과 이진 탐색이 있다.

## 선형 탐색 (Linear Search)


- 맨 앞이나, 맨 뒤부터 순서대로 하나하나 찾아보는 알고리즘으로 가장 단순하고 간단한 탐색 알고리즘
- 알고리즘 단계
1. 배열의 첫번째 원소부터 시작한다.
2. 현재 원소와 찾는 값을 비교한다.
3. 찾는 값과 현재 원소가 같으면 탐색을 종료하고 인덱스를 반환한다.
4. 배열의 마지막 원소까지 탐색한 경우, 찾는 값이 배열에 없다는 것을 의미하므로 -1을 반환한다

### 선형 탐색 코드

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 반환
}

> 시간복잡도 : O(n) - 배열의 크기에 따라 시간이 늘어나므로

## 이진 탐색 (Binary Search)


- 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법
- **배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘**이다
- 알고리즘 단계
1. 배열의 첫번째 원소와 마지막 원소를 더한 후, 2로 나눈다. 이를 중간값으로 설정한다.
2. 중간값과 찾는 값을 비교한다.
3. 중간값이 찾는 값보다 크다면, 배열의 왼쪽 절반에서 탐색을 반복한다.
4. 중간값이 찾는 값보다 작다면, 배열의 오른쪽 절반에서 탐색을 반복한다.
5. 찾는 값과 중간값이 같으면 탐색을 종료하고 인덱스를 반환한다.
6. 배열의 모든 원소를 탐색한 경우, 찾는 값이 배열에 없다는 것을 의미하므로 -1을 반환한다.

### 이진 탐색 코드

public static int binarySearch(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;

    while (left <= right) {
        int mid = (left + right) / 2;

        if (arr[mid] == target) {
            return mid; // 탐색 성공 시 인덱스 반환
        } else if (arr[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1; // 탐색 실패 시 -1 반환
}

> 시간복잡도 : O(logN)
> 2^n 개라면, 이진 트리를 사용할 경우 n번의 탐색을 통해서 원하는 값을 찾을 수 있게 된다.

---

# 정렬 알고리즘 (선택 정렬, 버블 정렬, 삽입 정렬)

- 데이터의 집합을 어떠한 기준(핵심항목, key)의 대소관계를 따져 일정한 순서로 줄지어 세우는 것
- 배열을 사용하여 오름차순으로 데이터를 정렬하는 방법을 알아보자

## 버블정렬 (Bubble Sort)

- 배열내의 두개의 인접한 Index를 비교하여 더 큰 숫자를 뒤로 보내 차곡차곡 쌓아 정렬하는 알고리즘


- 알고리즘 단계
1. 배열의 처음부터 끝까지 탐색하며, 인접한 두 요소를 비교합니다.
2. 인접한 두 요소 중 앞쪽의 값이 더 크다면, 두 요소의 위치를 교환합니다.
3. 배열의 끝까지 도달할 때까지 1단계와 2단계를 반복합니다.
4. 한 번의 탐색이 끝나면, 가장 큰 값이 배열의 끝으로 이동하게 됩니다.
5. 배열의 모든 요소에 대해 위 과정을 수행하면 정렬이 완료됩니다. 다음 탐색에서는 이미 정렬된 요소는 제외하고 탐색합니다.

### 버블 정렬 코드

public void bubbleSort(int[] array) {
    int n = array.length;

    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (array[j] > array[j + 1]) {
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
}

> 시간복잡도 : O(n^2)

## 선택 정렬 (Selection Sort)

- 최소값을 검색하여 배열의 왼쪽부터 순차적으로 정렬을 반복하는 정렬 알고리즘


- 알고리즘 단계
1. 배열의 처음부터 끝까지 탐색하며 최소값을 찾는다.
2. 최소값을 찾은 후, 현재 위치의 값과 최소값을 교환한다.
3. 현재 위치를 다음 위치로 이동한 뒤, 1단계부터 다시 반복한다.
4. 배열의 모든 요소에 대해 위 과정을 수행하면 정렬이 완료된다.

### 선택 정렬 코드

public void selectionSort(int[] array) {
    int n = array.length;

    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;

        for (int j = i + 1; j < n - 1; j++) {
            if (array[j] < array[minIndex]) {
                minIndex = j;
            }
        }

        int temp = array[minIndex];
        array[minIndex] = array[i];
        array[i] = temp;
    }
}

> 시간복잡도 : O(n^2)

## 삽입정렬 (Insertion Sort)

- 인덱스 1부터 왼쪽과 비교하면서 순차적으로 정렬을 반복하는 정렬 알고리즘


- 알고리즘 단계
1. 두 번째 요소부터 시작하여 현재 위치의 값을 임시 변수에 저장한다.
2. 현재 위치보다 앞쪽에 있는 모든 요소를 비교하며, 임시 변수에 저장된 값보다 큰 값을 발견하면 그 값을 오른쪽으로 한 칸 이동시킨다.
3. 큰 값을 발견하지 못하거나 배열의 시작에 도달하면, 임시 변수에 저장된 값을 빈 칸에 삽입한다.
4. 다음 위치로 이동하여 1단계부터 다시 반복한다.
5. 배열의 모든 요소에 대해 위 과정을 수행하면 정렬이 완료된다.

### 삽입 정렬 코드

public void insertionSort(int[] array) {
    int n = array.length;

    for (int i = 1; i < n; i++) {
        int key = array[i];
        int j = i - 1;

        while (j >= 0 && array[j] > key) {
            array[j + 1] = array[j];
            j = j - 1;
        }
        array[j + 1] = key;
    }
}

> 시간복잡도 : O(n^2)