이진탐색, binary search, 코틀린

이진 탐색이란? 

이진 탐색이란 데이터가 정렬돼 있는 배열에서 특정한 값을 찾아내는 알고리즘 입니다. 배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값 X와 비교합니다. X가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터들을 대상으로, X가 중간값보다 크면 배열의 우측을 대상으로 다시 탐색합니다. 동일한 방법으로 다시 중간의 값을 임의로 선택하고 비교합니다. 해당 값을 찾을 때까지 이 과정을 반복합니다.

 

 

아래의 배열에서 17 을 이진 탐색으로 찾아보자.

{ 17, 28, 43, 67, 88, 92, 100, 200 }
중간 값 : 88 -> 작다 -> { 17, 28, 43, 67 }
중간 값 : 43 -> 작다 -> { 17, 28 }
중간 값 : 28 -> 작다 -> { 17 }
중간 값 : 17 -> 종료

 

---

코드로 나타낸 이진 탐색

 

fun bSearch(target: Int, arr: List<Int>): String {
	// target : 찾을 숫자
    var low = 0
    var high = arr.lastIndex
    var mid = 0

    while (low <= high) {
        mid = (low + high) / 2		// 중간 인덱스 

        when {
            arr[mid] < target   -> low = mid + 1	// 타겟이 중간값보다 크기 때문에 중간값을 기준으로 오른쪽을 탐색 해야 하기 때문에 low 인덱스를 mid + 1로 재설정
            arr[mid] > target   -> high = mid - 1	// 타겟이 중간값보다 작기 때문에 중간값을 기준으로 왼쪽을 탐색 해야 하기 때문에 high 인덱스를 mid -1 로 재설정
            arr[mid] == target  -> return "1 "
        }
    }

    return "0 "
}

 

 

---

출처

https://cjh5414.github.io/binary-search/

이진 탐색(Binary Search) 알고리즘 개념 이해 및 추가 예제