[이진 탐색] 이진탐색 방법 & 자바 코드

이진탐색

이진 탐색은 정렬된 리스트에서 검색 범위를 절반씩 줄여가며 탐색하는 알고리즘이다.

시간복잡도: O(log n)

 

이진탐색 하는 방법

1. 이진탐색할 배열을 정렬한다.

2. 처음에는 배열의 0번째 인덱스를 left로 마지막 인덱스를 right로 한다.

3. left와 right의 중간 즉,(left+right)/2 지점을 mid로 한다.

4. 4-3조건을 만족하거나 5의 조건을 만족할때까지 반복한다.

    4-1 mid < key면 left = mid + 1을 하여 left의 값을 갱신하고 새로운 mid값을 구한다.

    4-2 mid > key면 right= mid - 1을 하여 right의 값을 갱신하고 새로운 mid값을 구한다.

    4-3 mid == key 값이면 배열에 찾는 값이 존재하는 것이다.

5. right<left가 되었는데 key값을 찾지 못했다면 찾는 값이 배열에 존재 하지 않는 것이다

예제1

예제2

이진탐색 자바 코드

1. 반복문을 활용한 코드

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

    while (left <= right) {
        int mid = (left + right) / 2;    // 중간위치

        if (key < arr[mid]) right = mid - 1;  // key값이 중간보다 작을때
        else if (key > arr[mid]) left = mid + 1; // key값이 중간보다 클때
        else return true;  // key값과 중간값이 같을때
    }
    return false; // 값이 존재 하지 않을때
}

2. 재귀를 활용한 코드

public static boolean binarySearch(int[] arr, int key, int left, int right) {
        if(left > right) return false;

        int mid = (left + right) / 2;

        if (arr[mid] < key)
            return binarySearch(arr, key, mid +1, right);
        else if (arr[mid] > key)
            return binarySearch(arr, key, left, mid - 1);
        else
            return true;
    }