이진탐색

 

 

 
 
fun binary_search(arr:List<Int>, find: Int, start: Int, end: Int): Int {
    if(start>end) {
        return -1
    }
    val mid = (start+end)/2
    if(arr[mid]==find){
        return mid
    }
    else if(arr[mid]>find){
        return binary_search(arr,find,start,mid-1)
    }
    else{
        return binary_search(arr,find,mid+1,end)
    }
}
 
fun main(){
    val (num , find)= readLine()!!.split(" ").map{it.toInt()}
    val arr = readLine()!!.split(" ").map{it.toInt()}
 
    val result = binary_search(arr,find,0,num-1)
 
    if(result==-1)
        println("원소가 존재하지 않습니다.")
    else{
        println(result+1)
    }
}

반복문 버전.

 
 
fun binary_search(arr:List<Int>, find: Int, start: Int, end: Int): Int {
    var end = end
    var start = start
    var mid = start + end /2
    while(start<=end){
        mid = start + end /2
        if(arr[mid]==find){
            return mid
        }
        else if(arr[mid]>find){
            end = mid-1
        }
        else{
            start = mid+1
        }
    }
    return -1
}
 
fun main(){
    val (num , find)= readLine()!!.split(" ").map{it.toInt()}
    val arr = readLine()!!.split(" ").map{it.toInt()}
 
    val result = binary_search(arr,find,0,num-1)
 
    if(result==-1)
        println("원소가 존재하지 않습니다.")
    else{
        println(result+1)
    }
 
}

 
 
fun binary_search(arr:List<Int>, num:Int, find: Int, start: Int, end: Int): Int {
    var end = end
    var start = start
    var mid = (start + end) /2
    var total = 0
    while(start<=end){
 
        total=0
        mid = (start + end) /2
        for(i in 0 until num){
            if(arr[i]-mid>0)
                total+=(arr[i]-mid)
        }
        //println("start: $start, end: $end, mid: $mid total: $total")
        //println(mid)
        if(total==find){
            return mid
        }
        else if(total>find){
            start = mid+1
        }
        else{
            end = mid-1
        }
    }
    return mid
}
 
fun main(){
    val (num , want)= readLine()!!.split(" ").map{it.toInt()}
    val arr = readLine()!!.split(" ").map{it.toInt()}
    val end = arr.maxByOrNull { it }!!.toInt()
    println(end)
    val result = binary_search(arr,num,want,0,end)
 
 
    println(result)
 
 
}