코틀린의 이진탐색

이진탐색이니 당연히 정렬되어있어야함

 

 

정확한 해당값 인덱스검색

abcList.binarySearch(조회할값)

이경우 정확히 해당값이 있으면 해당 인덱스리턴,없으면 음수리턴

 

해당값이 들어갈자리 찾기는 만약 같은수가 여러개있을경우,왼쪽끝인덱스를 받냐 오른쪽끝인덱스+1를 받냐에 따라 2개로 나뉨

lowerBound(listOf(1,2,3,3,3,5),3) //2
upperBound(listOf(1,2,3,3,3,5),3) //5
lowerBound(listOf(1,2,3,3,3,5),4) //5
upperBound(listOf(1,2,3,3,3,5),4) //5

왼쪽끝인덱스는

    fun lowerBound(calList:List<Int>,target:Int):Int{
        var left=0
        var right=calList.size
        while (left<right){
            val mid=(left+right)/2
            if(calList[mid]<target){
                left=mid+1
            }else{
                right=mid
            }
        }
        return right
    }

오른쪽끝인덱스+1은(해당값을 초과하는 첫번째숫자)

    fun upperBound(calList:List<Int>,target:Int):Int{
        var left=0
        var right=calList.size
        while (left<right){
            val mid=(left+right)/2
            if(calList[mid]<=target){
                left=mid+1
            }else{
                right=mid
            }
        }
        return right
    }