[알고리즘] Binary Search

Binary Search 란?

Binary Search(이진탐색) 이란 유명한 탐색알고리즘 중 하나다.

정렬된 데이터를 이분화 해서 찾고자하는 값을 구하는 구조이다. 여기서 말하는 "이분화" 는 데이터를 절반으로 나누는 것을 의미한다.

나눈 데이터를 중간점(median) 기준으로 탐색하고자하는 값이랑 비교, 비교했을때 크거나 작거나에 따라서 절반의 데이터를 버리고 남은 데이터를 반으로 또 나누고 이 과정을 반복한다. 탐색하고자 하는 답이 나오거나 더 이상 못나누는 상황에 도달할때까지.

그림으로 보면 더 단순하다.

시각화에는 실패했다... :)

설명 ㄱㄱ

# 6개의 숫자가 있음.

# 여기서 4 라는 숫자를 찾아보자. 
# 첫번째 검색인 만큼 검색 범위는 전체 숫자다 (1~6) 
# 1을 시작점, 6을 끝점으로 설정한다.

1 2 3 4 5 6
s         e

# 데이터를 반으로 나누기 위해 중간점을 구한다. (6+1)/2 = 3

1 2 3 4 5 6
s   m     e

# 데이터를 비교한다. (3과 4 비교)
1) 중간점 3은 찾고자 하는 4와 같이 않다.
2) 중간점 3은 찾고자 하는 4보다 작다.

# 중간점이 찾고자하는 값보다 작으니 중간점 기준 위에서 검색한다. 검색 번위 재설정을 위해 시작점을 중간점 보다 높게 설정한다


1 2 3 4 5 6
    m s   e

# 범위가 변경됬으니 중간점을 다시 계산한다. (4+6) /2 = 5
1 2 3 4 5 6
      s m e

# 데이터를 비교한다. (5와 4 비교)
1) 중간점 5는 찾고자 하는 4와 같이 않다.
2) 중간점 5는 찾고자 하는 4보다 크다.

# 중간점이 찾고자하는 값보다 크니 중간점 기준 아래에서 검색한다. 검색 번위 재설정을 위해 끝점을 중간점 보다 낮게 설정한다.

1 2 3 4 5 6
      s m 
      e

# 범위가 변경됬으니 중간점을 다시 계산한다. (4+4) /2 = 4
1 2 3 4 5 6
      s
      e


# 데이터를 비교한다. (4와 4 비교)
1) 중간점 4는 찾고자 하는 4와 같이 않다. 


# 결국 4라는 값이 존재하는걸 확인할 수 있었다.

binary search 의 시간복잡도는 OLogN 이라고 한다.

자바로 발코딩한 이진 탐색

// 데이터를 배열로 저장되어 있고 정렬이 되어 있다.

int start = 0;  
int end = arr.length -1;

// data를 찾았거나 더이상 찾을 수 없는 상태 (start가 end 보다 큰 경우 모든 데이터를 다 찾아 봤다라고 정의할 수 있다)  
while ( start >= end ) {  
    // 중간점을 구한다  
    int middle = (start + end) / 2;

    // 중간점과 탐색하고자 하는 값이랑 비교한다 같으면 검색 종료
    if (middle == search) return true;

    // 아니면 계속 찾는다. 이때 검색하고자 하는 숫자가 중간점보다 큰지 작은지 분석한다.
    if (middle > search) {
         // 중간값이 크면 끝을 다시 설정한다
         end = middle -1;
    } else {
         // 중간값이 더 작으면 시작점을 다시 설정한다.
         start = middle+1
    }

    // 해당 프로세스를 반복한다.
}

// 끝까지 못찾으면 false 리턴한다
return false

추가적으로 Arrays 클래스에도 binarySearch 함수가 존재한다.

해당 함수에서는 존재 시 element의 idx를 return 해주고,

해당 element가 없을 시 음수로 element가 존재했으면 들어갈 idx 를 보여준다.

// java 자체헤서 구현되어 있는 바이너리 서치를 사용해봄

int idx = Arrays.binarySearch(bookShelf,"ttest");
// 존재 시 검색된 element의 위치를 보여줌
// 없을 시 해당 element(key)가 Array 어던 위치에 들어가 있을지 표기해줌