[Swift] 이분탐색 BOJ 단계별로 풀어보기 + upper bound/lower bound (1654/2805/2110/1300/12015)

var input:[Int] = readLine()!.split(separator:" ").map{Int($0)!}
var N:Int = input[0]
var K:Int = input[1]
var lans:[Int] = []

for _ in 0..<N{
    lans.append(Int(readLine()!)!)
}

var first:Int = 1
var last:Int = lans.max()!
var result_length = 1

while first <= last{
    let half = (first+last)/2
    var result_lan = 0
    for i in lans{
        result_lan += i/half
    }
    if result_lan>=K {
        result_length = max(result_length,half) 
        first = half+1
        }
    else {last = half-1}
}
print(result_length)

var input:[Int] = readLine()!.split(separator:" ").map{Int($0)!}
var N:Int = input[0]
var K:Int = input[1]
var trees:[Int] = []
input = readLine()!.split(separator:" ").map{Int($0)!}
for i in 0..<input.count{
    trees.append(input[i])
}

var first:Int = 0
var last:Int = trees.max()!
var result_length = 0

while first <= last{
    let half = (first+last)/2
    var result_K = 0
    for i in trees{
        if i-half > 0{
            result_K += i-half
        }
    }
    if result_K>=K {
        result_length = max(result_length,half) 
        first = half+1
        }
    else {last = half-1}
}
print(result_length)

var input:[Int] = readLine()!.split(separator:" ").map{Int($0)!}
var N:Int = input[0]
var C:Int = input[1]
var houses:[Int] = []
for _ in 0..<N{
    houses.append(Int(readLine()!)!)
}

var result:Int = 1
var first:Int = 1
var last:Int = houses.max()!
houses.sort()

while first<=last {
  let mid:Int = (first+last)/2
  var count:Int = 0
  var stack:[Int]=[]
  for i in 0..<N {
    if(i==0||(houses[i]-stack.last!)>=mid){ //스택에 아무것도 없거나 넣을 공유기가 조건을 충족하는 경우
    stack.append(houses[i])
    }
    
    if N-i<C-stack.count{ //모든 공유기를 넣어도 공유기 수를 만족하지 못하는 경우
       break
    }
    else if stack.count==C { // 모든 공유기를 다 넣은 경우
      break
    }
  }
  if stack.count==C { //조건을 충족하여 최소 mid만큼 거리로 공유기를 다 넣은 경우
    result = max(result,mid)
    first = mid+1
  } // 조건을 충족하지 못한 경우
  else{last = mid-1}
} 

print(result)

import Foundation

var N:Int = Int(readLine()!)! 
var k:Int = Int(readLine()!)!

var first:Int = 1
var last:Int = N*N
while first<=last{
  let mid:Int = (first+last)/2
  var count:Int = 0

  for i in 1...N{
    count += min(mid/i,N)
  }
  if count>=k{
    last = mid-1 
  }else{first = mid+1}

}

print(first)

import Foundation

func Binary_Search(_ arr:[Int], _ find:Int)->Int{
  var first:Int = 0
  var last:Int = arr.count
  while first<last {
    let mid:Int = (first+last)/2
    if arr[mid]>=find {
       last = mid     
    }else{first = mid+1}
  }

  return first
}

var N:Int = Int(readLine()!)! 
var input:[Int] = readLine()!.split(separator:" ").map{Int($0)!}
var LIS:[Int] = []

for i in input{
  if LIS.isEmpty||LIS.last!<i{
    LIS.append(i)
    continue
  }
  else{
    LIS[Binary_Search(LIS,i)] = i
  }
}

print(LIS.count)

---

Lower Bound & Upper Bound

이분 탐색이 '원하는 값 k를 찾는 과정' 이라면
Lower Bound는 원하는 값 k 이상이 처음 나오는 위치를 찾는 방법
Upper Bound는 원하는 값 k를 초과한 값이 처음 나오는 위치를 찾는 방법이다.

결론적으로 이분 탐색은 이분 탐색 기준과 upper bound/lower bound를 잘 선택하는 것이 핵심인 것 같다.

​