이진 검색

검색은 주어진 요소 집합에서 특정 요소를 찾는 행위입니다. 이것은 정렬과 비슷해 보이지만 전체 요소 집합을 수행하는 대신 하나의 요소만 찾습니다.

일반적으로 검색에는 선형 검색 과 이진 검색 의 두 가지 일반적인 방법이 있습니다. 첫 번째 것은 가장 간단하며 찾고 있는 목록이 전혀 정렬되지 않은 경우에만 유용합니다. 0에서 배열의 길이까지 살펴보고 찾고 있는 요소인지 하나씩 확인하면 됩니다. 따라서 시간 복잡도는 O(n)입니다.

이것은 Swift의 선형 검색 구현입니다.

func linearSearch<T: Equatable>(_ a: [T], _ key: T) -> Int? {
for i in 0 ..< a.count {
        if a[i] == key {
            return i
        }
    }
return nil
}

linearSearch(numbers, 43)  // returns 15

다음은 7이 대상 값인 이진 검색 알고리즘의 시각화입니다.

위키피디아에서

실제로 어떻게 작동하는지 봅시다.

func binarySearch<T: Comparable>(_ a: [T], key: T, range: Range<Int>) -> Int? {
if range.lowerBound >= range.upperBound {
        return nil
    } else {
        let midIndex = range.lowerBound + (range.upperBound - range.lowerBound) / 2

        if a[midIndex] > key {
            return binarySearch(a, key: key, range: range.lowerBound ..< midIndex)
        } else if a[midIndex] < key {
            return binarySearch(a, key: key, range: midIndex + 1 ..< range.upperBound)
        } else {
            return midIndex
        }
    }
}

let numbers = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67]
binarySearch(numbers, key: 43, range: 0 ..< numbers.count)  // gives 13

다음은 Swift에서 이진 검색을 반복적으로 구현한 것입니다.

func binarySearch<T: Comparable>(_ a: [T], key: T) -> Int? {
var lowerBound = 0
    var upperBound = a.count
while lowerBound < upperBound {
        let midIndex = lowerBound + (upperBound - lowerBound) / 2
if a[midIndex] == key {
            return midIndex
        } else if a[midIndex] < key {
            lowerBound = midIndex + 1
        } else {
            upperBound = midIndex
        }
    }
return nil
}

마지막으로 다음과 같이 사용할 수 있습니다.

let numbers = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67]
binarySearch(numbers, key: 43)  // gives 13

실행 시간이 입력 크기의 로그에 비례하여 증가하기 때문에 이진 탐색 알고리즘 의 시간 복잡도 (두 접근 방식 모두)는 O(log n) 입니다. 중심 인덱스가 원하는 값과 직접 일치할 때 최상의 시간 복잡도는 O(1)입니다.

반복 의 공간 복잡도 는 O(1) 입니다. 재귀적 방법에서 공간 복잡도 는 O(log n) 입니다.

시간을 내어 이 기사를 읽어주셔서 감사합니다.

Suggested posts

“그 작은 섬이 모든 것을 바꾼다”

탑승자 경험을 향상시키기 위해 Lyft 실시간 활동을 설계한 방법

“그 작은 섬이 모든 것을 바꾼다”

차량 공유를 위한 게임 체인저 Lyft에서 우리가 하는 모든 일 중에서 라이더와 운전자 간의 픽업 안무는 가장 복잡하고 결과적인 것 중 하나입니다. 이 안무를 잘하는 것은 Lyft가 많은 일을 잘하는 것에 달려 있지만 단순히 라이더가 속도를 유지하는 것이 필수적입니다.

앱 라이프사이클

앱 라이프사이클

: 앱 시작부터 종료까지 주기 : 메모리나 데이터 관리로 사용성 ⬆️ 보안 처리 가능 UIApplication, AppDelegate 상황 : AppDelegate 객체가 UIApplication 객체에서 보낸 메시지를 받아 각각 실행하는 기능 정의 Not Running : 앱이 실행되고 있지 않은 상태Inactive : 앱이 실행되고 있지만 이벤트가 수신되지 않은 상태활성: 앱이 실행 중이고 이벤트가 발생한 상태백그라운드: 앱이 백그라운드에 있지만 코드가 실행 중인 상태서스펜드: 앱이 실행 중인 상태 AppDelegate.swift 파일 SceneDelegate에서 델리게이트 기능이 될 코드를 백그라운드에서 실행하지 않고 실행 iOS 13 이상부터 지원하는 다중 씬 기능에 잘 대응하기 위해 AppDelegate / SceneDelegate AppDelegate 1.

Related posts

안전한 작업 환경 조성

안전한 작업 환경 조성

“그는 내가 위험에 처했을 때 나를 지켜줄 것입니다. 그가 나를 그의 천막 안에 숨길 것이다.

지구를 구하고 돈을 버는 방법

지구를 구하고 돈을 버는 방법

페트병, 유리병, 알루미늄캔, 그린에너지 패키지를 무심코 버린 적이 몇 번이나 되셨나요? 재활용에 대한 대가로 무언가를 얻을 수 있기를 몇 번이나 바랐습니까? 당신이 대부분의 사람들과 같다면 대답은 아마도 여러 번일 것입니다. 재활용은 종종 번거로움, 자질구레한 일 또는 즉각적이거나 실질적인 혜택을 가져오지 않는 의무로 간주됩니다.

Work Week에서의 학습은 생각보다 중요합니다.

Work Week에서의 학습은 생각보다 중요합니다.

우리는 종종 우리에게 좋다고 알고 있는 것을 구현하는 데 어려움을 겪고 있습니다. 중요한 다른 사람에게 우리가 그들을 사랑한다고 말하는 것부터 해적처럼 이야기하는 것을 기억하는 것까지, 그들이 이미 그런 일을 하고 있기 때문에 하루, 일주일 또는 한 달의 이벤트가 필요하지 않다고 주장하는 사람들이 항상 있을 것입니다.

일부 프리랜서가 자신의 삶을 속이는 이유

일부 프리랜서가 자신의 삶을 속이는 이유

나는 최근에 세계 최대의 전문 소셜 네트워크인 Linkedin에 있었고 내가 팔로우하는 프리랜서 디자이너의 게시물을 발견했는데 내 관심을 끌었습니다. 그들은 모두 비행기에서, 노트북과 함께 해변에서, 수영장에서, 멋진 전망이 있는 사무실에서 사진을 게시했습니다.