이진 탐색 (Binary Search)

1. 개념 설명

(1) 이진 탐색은 정렬된 배열에서 검색 범위를 줄여 나가면서 원하는 데이터를 검색하는 알고리즘이다.

 

(2) 이진 탐색은 오름차순으로 정렬된 정수의 리스트를 같은 크기의 두 부분 리스트로 나누고 필요한 부분

에서만 탐색하도록 제한하여 원하는 원소를 찾는 알고리즘이다.

 

 

 

 

2. 과정

by wiki

- 실제로 수행되는 과정이다.

 

 

 

 

3. 코드

public class BinarySearch {
    static int[] A = { 7, 2, 8, 10, 1 };
 
    public static void main(String[] args) {
        Arrays.sort(A);
        solve(10, 0, A.length-1);
    }
    
    public static void solve(int a, int low, int high){
        int mid=0;
        
        while(low<=high) {
            mid = (low+high)/2;
            
            if(A[mid]==a) {
                break;
            }else if(A[mid] < a) {
                low = mid+1;
            }else {
                high = mid-1;
            }
        }
        System.out.println(mid + " 인덱스 위치에 있습니다. ");
    }
}

 

 

 

 

4. 시간 복잡도

(1) 이진 탐색의 시간복잡도는 O(logN)이다.

 

 

 

 

5. 공간 복잡도

(1) 주어진 배열 안에서 정렬이 일어나므로, 공간 복잡도는 O(1)이다.