4장, 이분법

Introduction

이분법 사고방식에 대해서 설명하는 장이다.

Content

1. 무엇을 이분법 이라고 하는가?

하나를 두개로 나누는 방법이나 두개 중 하나를 고르는 방법을 이분법이라고 한다.

2. 어디에 이분법을 사용 하는가?

프로그래밍에선 정말 많이 쓰인다. 대표적으로 이진트리 검색을 들 수 있다. if ~ else 문도 이분법이다. 유명한 문제로는 "몇층에서 떨어졌는가?" 를 맞출 때 사용 한다.

참조 링크

• http://ja.wikipedia.org/wiki/이분법 <-- 번역기 돌리시길
  

Digression

함수 복잡도를 표기하기 위해 O 표기법을 사용하는데, 이때 log2^n 로 표기 된다. 여기서 n은 모든 경우의 수이다. 여기서 2가 바로 이분 검색을 의미한다.