C언어 | 이진검색(Binary Search) | 자료구조
이진검색은 데이터가 키 값으로 정렬이 되있어야 제대로된 검색이 가능하다. 예를 들어 아래와 같은 오름차순 정렬한 배열이 있다. [1, 3, 5, 7, 9, 11, 13, 15, 17, 19] 0 1 2 3 4 5 6 7 8 9 아래의 숫자는 배열의 인덱스다. 여기서 15를 검색한다. 이진 검색은 양끝이 필요하다. 인덱스 0과 9 를 더해서 2로 나눈다. 나머지를 버리면 4가 나온다. 이것이 배열의 중앙에 있는 값이다. array[인덱스 중앙] 인 array[4] = 9 를 얻는다. array[4] = 9 와 키값인 15를 비교한다. 키값이 더 크다. 오름 차순 정렬이니까 찾는 값은 9보다 오른쪽에 있어야 한다. 현재 9는 인덱스의 중앙에 있다. 왼쪽의 범위였던 0을 중앙인덱스 + 1인 5로 위치시킨다. ..