오늘 공부

이분탐색(Binary Search) 입력 : 정렬된 원소리스트, 찾을 값 시간복잡도 : log2 n 이분탐색 과정 정수 배열 int[] array = {2, 5, 8, 10, 15, 16, 19, 20}에서 int key = 8이 몇 번째에 위치해 있는지 찾는다고 가정하자. 가장 먼저 할 일은 탐색 범위를 정하는 것이다. 이 경우에는 주어진 정수 배열 전체를 기준으로 하므로 인덱스 0 ~ 7이 범위가 된다. 탐색 범위가 정해지면 해당 범위의 가운데에 위치한 값을 찾는다. 가운데 값은 탐색 범위의 마지막 인데스에서 첫 인덱스를 뺀 뒤 2로 나눈 수를 인덱스로 가지는 값이다. 이 경우는 (7 - 0) / 2는 3이므로 array[3]의 10이 가운데 값이 된다. key값과 가운데 값(10)을 비교한다. 1)..