[자료구조] 23 이진탐색

📌이진탐색 (Binary Search)

탐색시간을 줄이기 위하여 항목들을 정렬한 후에 탐색을 적용

 

✔️알고리즘

1. 오름차순으로 정렬된 항목들에 대해 가운데 median을 찾아 key와 비교한다

2. key=median이면 중간값의 인덱스를 반환하고 탐색을 종료한다

3. 탐색 키가 중간 값보다 작으면 중간 값의 왼쪽만 탐색하면 된다, 반대면 오른쪽만 

4. 변경된 탐색 대상 항목들에 대해 탐색 반복한다

 

 

📌시간복잡도: O(log_2n)

public class BinarySearch {
    public static void main(String[] args) {
        int n = 9;
        int pos;
        int key = 23;
        int[] num = {0, 1, 5, 9, 13, 17, 23, 32, 45};
        pos = binary_search(num, key, 0, n - 1);
        if (pos == -1) {
            System.out.println("Cannot find!");
        }
        else {
            System.out.println(pos);
        }
    }

    public static int binary_search(int num[], int key, int left, int right) {
        while (left <= right) {
            int med = (left + right) / 2;
            if (num[med] == key) {
                return med;
            } else if (num[med] < key) {
                left = med + 1;
            } else if (num[med] > key) {
                right = med - 1;
            }
        }
        return -1;
    }
}
//key=23 일 경우 6출력
//key=100 일 경우 Cannot find!출력

재귀 방식으로 return binary_search 도 가능하다 

여기서 중요한 부분은

👉 while(left<=right) 

이 부분이 없으면 엉키고 stack overflow가 될 수도 있기에 잘 생각해야 한다❗️