13. 정렬(Sort) - 이진탐색(Binary Search)

1. 이진탐색(Binary Search)의 개념

오름차순 정렬되어 있는 리스트 내에서 특정 값의 인덱스를 찾는 알고리즘

O(N)의 시간복잡도에 비하여 빠른 속도를 가지는 시간복잡도 O(logN)

그러나, 정렬된 리스트에서만 사용이 가능하다.

---

2. 이진탐색(Binary Search) 구현 - JAVA

package sort;

public class BinarySearch {

    public int search(int[] arr, int target) { // 정렬된 리스트 , 타겟 데이터를 받는다.

        // 1. 데이터의 중간 인덱스 값을 찾는다.
        // 2. 중간 인덱스 위치를 기준으로 arr을 절반으로 나눈다.
        // 3. 나눠진 절반의 리스트에서 target 값을 찾는다.

        int l = 0;      // 리스트의 가장 왼쪽 인덱스
        int r = arr.length - 1;  // 리스트의 가장 오른쪽 인덱스

        int m;      // 중간 인덱스
        while (l <= r) {
            m = l + ((r - l) / 2);  // overflow exception

            if (arr[m] == target) {
                return m;
            }

            if (arr[m] < target) {  // target 값이 더 큰 경우
                l = m + 1;
            } else {    // target 값이 더 작은 경우
                r = m - 1;
            }
        }
        return -1;
    }
}

---

3. 이진탐색(Binary Search) 구현 - Python

def binary_search(arr, target):
    l = 0
    r = len(arr) - 1

    while l <= r:
        m = (l + r) // 2
        if arr[m] < target:
            l = m + 1
        elif arr[m] > target:
            r = m - 1
        else:
            return m
    
    return -1



if __name__ == "__main__":
    arr = [1,2,3,4,5,6,7,8,9]
    print(binary_search(arr, 3))
    print(binary_search(arr, 7))
    print(binary_search(arr, 15))