[알고리즘] 패스트캠퍼스 챌린지 23일차

이진탐색(Binary Search)

• 탐색할 자료를 둘로 나누어 해당 데이터가 있을만한 곳을 탐색하는 방법

 

이진탐색과 순차탐색 비교

이진탐색이 순차탐색보다 속도가 빠르다.

 

분할 정복 알고리즘과 이진 탐색

• 분할 정복 알고리즘 (Divide and Conquer)
  • Divide: 문제를 하나 또는 둘 이상으로 나눈다.
  • Conquer: 나눠진 문제가 충분히 작고, 해결이 가능하다면 해결하고, 그렇지 않다면 다시 나눈다.
• 이진 탐색
  • Divide: 리스트를 두 개의 서브 리스트로 나눈다.
  • Comquer
    • 검색할 숫자 (search) > 중간값 이면, 뒷 부분의 서브 리스트에서 검색할 숫자를 찾는다.
    • 검색할 숫자 (search) < 중간값 이면, 앞 부분의 서브 리스트에서 검색할 숫자를 찾는다.

 

이제 이진탐색 알고리즘 코드로 작성해보기!!

배열에서 데이터가 있는지 없는지를 찾는다.

검색할 숫자(searchData), 배열(Data)

1. 배열 데이터 갯수가 1개인데 그 숫자가 검색할 숫자라면 -> return true

2. 배열 데이터 갯수가 1개인데 그 숫자가 검색할 숫자가 아니면 -> return false

3. [혹시 모를 방어코드] 배열이 비어있다면 -> return false

4. 배열 데이터 갯수가 2개 이상일 때

  - 배열을 반으로 나눈다.

  - 검색할 숫자가 배열의 중간값보다 크면 ? 배열 중간값부터 끝까지의 배열 내에서 찾는다. 계속 재귀호출해주면서 찾는다.

  - 검색할 숫자가 배열의 중간값보다 작으면 ? 배열 첫번째부터 중간값까지의 배열 내에서 찾는다. 계속 재귀호출해주면서 찾는다.

 

요거 그대로 Swift로 작성해보고 테스트도 해봤다.

func binarySearch(data: [Int], searchData: Int) -> Bool {
    
    if data.count == 1 && searchData == data[0] {
        // find!!
        return true
    }
    
    if data.count == 0 {
        return false
    }
    
    if data.count == 1 && searchData != data[0] {
        return false
    }
    
    let middle: Int = data.count / 2
    if searchData == data[middle] {
        // find!
        return true
    } else {
        if searchData > data[middle] {
            return binarySearch(data: Array(data[middle..<data.count]), searchData: searchData)
        } else {
            return binarySearch(data: Array(data[0..<middle]), searchData: searchData)
        }
    }
}

 

순차 탐색 (Sequential Search)

• 탐색은 여러 데이터 중에서 원하는 데이터를 찾아내는 것을 의미
• 데이터가 담겨있는 리스트를 앞에서부터 하나씩 비교해서 원하는 데이터를 찾는 방법

 

순차탐색은 그냥 첫번째부터 순서대로 쭉 탐색하는것..!

// return index
func sequentialSearch(data: [Int], searchData: Int) -> Int {
    for index in 0..<data.count - 1 {
        if data[index] == searchData {
            return index
        }
    }
    
    return -1
}

배열의 앞에서부터 순서대로 탐색하다가 찾으려는 데이터가 있으면 해당 인덱스를 리턴해주는 함수다.

배열에 찾는 데이터가 없으면 -1을 리턴한다.

 

 

오늘은 순차탐색과 이진탐색 알고리즘 구현했다.

예전에 어려웠는데.. 듣다보니 들을만했음!! ㅎㅎ

 

 

https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.