[Algorithm, Swift] 이분탐색 Binary Search 소스코드 초간단!

스위프트로 풀어보는 이분탐색 Swift로 간단하게 구현

 

안녕하세요 이웃님들 ! 오늘은 이분탐색 알고리즘에 대해 알아보도록 하겠습니다.

이분탐색은 전체를 다 돌면서 확인하는 순차탐색보다 효율성이 좋기 때문에 

알고리즘 문제 내에서 탐색이 필요하실 때 꼭 활용해보셨으면 좋겠습니다! 

 

이분탐색이란?

이분탐색으로 정답을 찾고있는 쌈디

이분탐색! 두개로 나누어서 탐색한다는 뜻이죠? 

어떤 숫자를 찾으려고 할때 처음부터 하나하나 확인하면 숫자가 N개면 N번 다 돌아야 하는데

숫자들이 정렬이 되어있다는 전제하에 중간값과 비교를 하면서 업다운을 계속 하는거라고 생각하시면 됩니다. 

 

그런데 업다운 게임하실 때 제일 효과적으로 정답을 찾는 방법이 무엇일까요?

만약 터키가 한반도보다 52배라고 했는데, DOWN이라고 하면

그 다음에 무슨 숫자를 말해야 확률적으로 가장 정확할까요? 당연히 26입니다. 왜냐구요? 

만약에 제가 8이라고 했어요. 근데 UP이래요. 그러면 남아있는 숫자가 44개 잖아요? 그 중에 골라야되니까 확률도 떨어지겠죠 ㅠㅠ

그래서 26이라고 했는데 만약에 DOWN이래요. 그러면 27~51 까지를 전부 버릴수 있으니까 찾을 확률이 더 높아지겠죠? ㅎㅎ

 

사진 속 사이먼디 처럼 여러분도 일상속에서 업다운 게임 많이 하시죠? 알고리즘에서도 그것이 가능합니다~!!

 

그러면 이제 소스코드를 보면서 이해해 보도록 합시다~!!

 

재귀적으로 이분탐색 표현하기

DFS, BFS문제를 풀 때 자주사용했던 재귀적으로 문제를 해결하는 방법입니다. 

이분탐색에서도 활용해보도록 하겠습니다. 

//재귀적으로 표현한 이분탐색
//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)

 

반복문으로 이분탐색하기

반복문 구현을 하시면 좀더 직관적으로 이해가 잘 가실겁니다!

while문을 활용해 보도록 하겠습니다.

종료조건이나 기본 로직은 사실상 재귀형태와 똑같습니다!

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

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)

 

이것으로 스위프트 Swift로 작성하는 이분탐색 알고리즘에 대해서 알아봤는데요!

혹시 궁금한 점이 있으시다면 언제든 편하게 말씀해주세요! 

참고로 반환되는 값은 타겟 숫자의 인덱스를 반환하도록 쓰여져 있습니다.

 

더 많은 알고리즘과 소스코드는 아래 레포지토리에서 확인이 가능합니다.

제가 복기 가능한 회사의 코딩테스트 문제들도 변형하여 올릴 예정이니

혹시 코딩테스트를 Swift로 준비하실 분들이라면 star 를 해두시면 좋습니다! 

 

GitHub - AnnaBaeTofuMom/TodayILearned: 새롭게 배운 것을 기록합니다, 나의 언어로 새로 씁니다.

 

감사합니다!