이진탐색

분할 정복 알고리즘 정의

• 분할 정복 알고리즘 (Divide and Conquer)
  • Divide: 문제를 하나 또는 둘 이상으로 나눈다.
  • Conquer: 나눠진 문제가 충분히 작고, 해결이 가능하다면 해결하고, 그렇지 않다면 다시 나눈다.

이진 탐색 정의

 

• Divide: 배열을 두 개의 서브 배열로 나눈다.
• Conquer
  • 검색할 숫자 (search) > 중간값 이면, 뒷 부분의 서브 배열에서 검색할 숫자를 찾는다.
  • 검색할 숫자 (search) < 중간값 이면, 앞 부분의 서브 배열에서 검색할 숫자를 찾는다.

// 이진탐색
func binarySearch(dataArray: [Int], search: Int) -> Bool {
    if dataArray.count == 1 && dataArray[0] == search {
        return true
    }
    
    if dataArray.count == 1 && dataArray[0] != search {
        return false
    }
    
    if dataArray.count == 0 {
        return false
    }
    
    let medium = (dataArray.count / 2) - 1
    
    if dataArray[medium] == search {
        return true
    } else {
        if dataArray[medium] < search {
            return binarySearch(dataArray: Array(dataArray[(medium + 1)...]), search: search)
        } else {
            return binarySearch(dataArray: Array(dataArray[...medium]), search: search)
        }
    }
}
let array = [1,6,2,4,5,2]
print(binarySearch(dataArray: array.sorted(), search: 6))