팁 : 이진검색

그냥 단순한 테크닉인데요(당연히 모두 알고계시리라 생각하지만, 그래도 모르시는 분이 있을까봐 써봅니다)

어떤 배열에서 값을 서치하고 싶을때 처음부터 끝까지 훑지 마시고

변수 3개를 추가로 생성하셔서(start,end,mid 이런식으로)

start는 서치를 하실 배열 시작부분

end는 끝부분(취향에 따라서 +1해주시는 것도.. 저는 +1합니다)

mid 는 start와 end의 중간값으로 정합니다.(참고 : 실수로 하지 마세요.)

방법은 이렇습니다.

배열이 어떤 기준하에 정렬되어 있을때

그 기준에서 배열[mid]의 값이 어떤상태인지 따라

범위를 반씩 뭉텅뭉텅 줄여가는 겁니다.

예를 들어보겠습니다.

 

어떤 잉간이 자신의 나이를 맞추라고 문제를 냈습니다.(범위는 1~100)

단, 이 잉간은 우리가 숫자를 불렀을때 자신의 나이가 그 숫자보다 큰지, 적은지를 알려주지만

숫자를 7번 이상 부를 수 없습니다.

자, 이것을 이진 검색의 개념을 적용시켜 보겠습니다.

start : 0 end : 101 mid : 50(저는 코딩의 편의를 위해 엔드값을 100보다 1 크게,start는 1보다 1 작게 잡겠습니다.)

네 나이는 50인가? -> output : 그보다 작다

start : 0 end : 50 mid : 25(end값을 mid값에 넣어줍니다.)

네 나이는 25인가? -> output : 그보다 크다

start : 25 end : 50 mid : 37

네 나이는 37인가? -> output : 그보다 작다

start : 25 end : 37 mid : 31

네 나이는 31인가? -> output : 그렇다

귀찮아서 이쯤 끝내겠습니다 -_-;;

어쨌든 제가 말하고 싶은 것을 이해하셨으리라 믿습니다.

이런 식으로 배열에서 값을 서치하면 빠른 속도로 값을 찾아낼 수 있습니다.

사실 이놈의 이진검색은 알고리즘에서 시간복잡도 줄이는데 굉장히 유용합니다.

N을 log₂N으로 만들어버리니깐요....

 

PS 대충대충 설렁설렁써서인지 이해하시기 힘들지도 모른다는 생각이 드네요.

그 점에 대해 사과를 드리는 의미에서 질문에 성심성의껏 답하겠습니다.

 

PS PS 호응이 좋다면 기본 알고리즘들을 올려볼 생각입니다.

 

본격 자료구조 공부하는 글

팬더는불륜마스터// 자료구조의 기초중 기초죠... 하지만 유용해요!

이거 영어이름만 알고있었는데 우리나라말론 이진검색이군효 ~

멜로군//영어로는 binary search라고 하는걸로 알고 있습니다.

과연 이걸 쓸만한수준의 복잡한정보를 가진 대형맵이 나올지.. ㅎ;;
다른 알고리즘도 올려보세요. 눈정화가 필요해요.