[알고리즘][KOTLIN] 이진 탐색

[알고리즘][KOTLIN] 이진 탐색

정의

입력된 배열이 오름 차순 혹은 내림 차순의 배열일 때 선형 탐색보다 빠르게 검색할 수 있는 알고리즘

검색 방법

배열을 오름 차순으로 정열 한다. 배열의 중앙 값을 찾는다. 검색하고자하는 값과 중앙값의 크기를 비교한다. 3번에서 중앙값이 클 경우 중앙 값 기준으로 왼쪽의 배열로 검색 값을 찾는다. 3번에서 중앙값이 작을 경우 중앙 값 기준으로 오른 쪽의 배열로 검색 값을 찾는다. 4, 5 번 과정을 반복한다.

코드

import java.util.* fun main(args: Array) { val sc = Scanner(System.`in`) print("요소수 : ") val num = sc.nextInt() val x = IntArray(num) { sc.nextInt() } x.sorted() print("$x") print("검색할 값 : ") val ky = sc.nextInt() val idx = binarySearch(x, num, ky) if (idx == -1) { println("검색결과가 없어요") } else { println("검색결과값이 위치 ${idx}에 있어요") } } private fun binarySearch(x: IntArray, num: Int, key: Int): Int { var firstIdx = 0 var lastIdx = num - 1 do { val midIdx = (firstIdx + lastIdx) / 2 when { x[midIdx] == key -> { return midIdx } x[midIdx] < key -> { firstIdx = midIdx + 1 } else -> { lastIdx = midIdx - 1 } } } while (firstIdx <= lastIdx) return -1 }

from http://jefflim-81.tistory.com/38 by ccl(A) rewrite - 2021-11-22 13:01:55