[Swift] 이진탐색(Binary Search)

이진탐색

데이터가 정렬되어있는 배열에서 중간값과 비교하며 특정한 값을 찾아내는 탐색 방법

구현

재귀

//재귀적으로 표현한 이분탐색
//11이 어디있는지 찾는 이분탐색입니다. 

var binaryArray = [0, 1, 4, 6, 8, 11, 14, 23, 24, 26, 28, 31, 41, 50]

func recursiveBinary(array: [Int], target: Int, start: Int, end: Int) -> Int? {
	//시작점이 끝점보다 커지면? 이미 모든 영역을 탐색했다는 뜻 이겠죠? 모든 영역을 탐색했는데 타겟 숫자를
    //못 찾았다면 nil을 리턴해 주도록 합시다. 
    if start > end {
        return nil
    }
    
    
    //일단 반으로 나눌거니까 중간을 찾아줍시다. 
    var mid = (start + end) / 2
    
    //중간값을 찾았는데 그게 타겟 숫자라면 그 값을 리턴해 줍니다.
    if array[mid] == target {
        return mid
    } else if array[mid] > target {
		//중간값과 타겟을 비교했는데 중간값보다 타겟 숫자가 작다면 시작점부터 중간값 바로 밑에까지를 다시 탐색하세요    
        return recursiveBinary(array: array, target: target, start: start, end: mid - 1)
        
    } else {
    	// 그 밖의 경우라면 중간값보다 타겟 숫자가 크다는 거겠죠? 중간값 바로 위부터 마지막까지를 다시 탐색하세요.
        return recursiveBinary(array: array, target: target, start: mid + 1, end: end)
    }
     
}

var recursiveResult = recursiveBinary(array: binaryArray, target: 11, start: 0, end: binaryArray.count - 1)
print(recursiveResult)

 

반복문

//반복문으로 구현한 이진 탐색 소스코드

func repetitionBinary(array: [Int], target: Int, start: Int, end: Int) -> Int? {
    //시작점과 끝점을 잡아주는건 동일합니다.
    var start = start
    var end = end
    
    //마찬가지로 시작점이 끝점보다 작은 동안, 즉 전체를 탐색하기 전까지 계속 돌아줍니다.
    while start <= end {
    	//중간값 잡는것도 똑같죠?
        var mid = (start + end) / 2
        
        //여기도 거의 유사한 방식입니다. 중간값이 타겟값이면 중간값을 리턴해주고
        if array[mid] == target {
            return mid
        } else if array[mid] > target {
        //중간값이 타겟 숫자보다 크면 그 다음 돌아갈때는 끝점을 중간값 밑까지로 바꿔주세요. 
            end = mid - 1
        } else {
        // 중간값이 타겟 숫자보다 작으면 그 다음 돌아갈때는 시작점을 중간값 바로 위까지로 바꿔주세요.
            start = mid + 1
        }
        
    }
    //위의 반복문에서 결과를 못찾아서 while문을 탈출하면 값이 그 안에 없는거니 nil을 반환해 주세요
    return nil
    
}

var result2 = repetitionBinary(array: binaryArray, target: 4, start: 0, end: binaryArray.count - 1)
print(result2)