Basic/Data Structure

Data Structures :: Binary Search (이진 탐색)

VallistA2015. 2. 23. 18:02

아마 탐색이 필요할때 일반적으로 사람들이 가장 많이 쓰는 구문은 for 일것이다.

배열의 자료중에 탐색이 필요해서 처음부터 끝까지 돌렸다고 가정하자. 그러면 우리는 어떻게 하게 될 것인가?

보통 for문을 처음부터 끝까지 돌리는 순차 탐색 (Linear Search) 를 사용하게 될 것이다.

하지만 과연 이 순차 탐색이 속도가 좋을 것 인가? 

배열 자료안에 5000만개씩이나 되는 자료가 있고, 5000만개 중에 거의 끝에 우리가 찾는 배열이 있다고 하면 순차 탐색으로는 거의 5000만개가 되는 배열에 접근해야 한다는 것인데 이것은 굉장히 안좋은 방법이 된다.

그래서 우리는 이진 탐색(Binary Search) 라고 하는 자료구조를 사용하여 조금 해소해보고자 한다.


보통 Binary Search를 사용하는 방법은 Recursive (재귀호출) 방법과 while로 함수 루프 내에서 돌리는 방법이 존재한다.

그 방법중에 먼저 while 루프 돌리는 방법을 소개하도록 하겠다.



Binary Search는 처음 부분과 끝 부분, 그리고 중간 부분으로 나누어지며 처음 부분과 끝 부분을 조절하므로써 획기적인 연산 속도를 제공한다. 처음 부분과 끝 부분의 평균을 도출해내어 중간을 잡고, 그 중간 지점을 기준으로 데이터의 위치를 가늠하는 방법이라고 생각하면 편하다.


현재 자신이 찾는 값이 적으면 최고 값이 그 적은 값의 인덱스 - 1 이 되며 새로운 최고점이 된다.

현재 자신이 찾는 값이 크면 최저 값이 그 큰 값의 인덱스 + 1이 되며 새로운 최저점이 되는 방식이다.


그림을 보면 이해가 빠를것이다.



그림에서 순서대로 보면,

1) 우리가 6이라는 값을 찾으려 한다. 

2) 9 ~ 1 범위에서 중간값을 도출한다. 그러면 4가 나온다. 4가 나오면 그 값이 우리가 찾는 값보다 작으므로 4 < 6 최고 값이 그 적은 값의 인덱스 - 1이 된다.

3) 그러므로 최고 값은 1에서 4가 되고, 9~4 범위내의 중간값을 도출하게 된다. int 형으로 인덱스를 도출하므로 9~4 의 중간값은 7이된다.

4) 근데 이제 7의 값은 6보다 크므로 7 > 6 최저값이 그 큰값의 인덱스 + 1이 되며 새로운 최저점이 된다. 즉 9는 6이 되므로 

6~4의 값을 도출하게되면 6으로 포커싱이 되므로 6=6이 맞게된다.


정말 쉬운 방법이다.


다음은 Recursive로 구현하는 방법을 보도록 하자.


 


Recursive도 구현 방법이 비슷하다.

한번 참고해서 보면 좋을 것 같다.

댓글

VallistA

병특이 끝나서 게임에서 웹으로 스위칭한 프로그래머.
프로그래밍 정보등을 공유합니다.
현재는 이 블로그를 운영하지 않습니다.
vallista.kr 로 와주시면 감사하겠습니다!

자고 싶습니다. ㅠㅠ

Github      :: 링크

궁금한점 문의 주시면 답변드리도록 하겠습니다

VISITED

Today :

Total :

SNS

  • 페이스북아이콘
  • 카카오톡아이콘
  • 트위터아이콘

Lately Post

Lately Comment