バイナリナビゲーション

20090 ワード

バイナリナビゲーションアルゴリズム#アルゴリズム# コーディングテスト swift テキストリンク

この文章は「就職のためのコードテストwith python」という本を勉強して記録しています.
しかし、iOSを勉強しているので、swift言語でコードを変換しています.

シーヶンスナビゲーション

リスト内の特定のデータを検索するには、前からデータを1つずつチェックします.
データが整列しているかどうかにかかわらず、前の要素から1つずつチェックします.
時間複雑度O(N)O(N)O(N)O(N)

func sequentialSearch(n: Int, target: String, array: [String]) -> Int {
    for i in 0..<n {
        if array[i] == target {
            return i + 1
        }
    }
    return -1
}

print("생성할 원소 개수를 입력한 다음 한 칸 띄고 찾을 문자열을 입력하세요.")
let inputs = readLine()!.split(separator: " ")
let n = Int(inputs[0])!
let target = String(inputs[1])

print("앞 서 적은 원소 개수만큼 문자열을 입력하세요. 구분은 띄어쓰기 한 칸으로 합니다.")
let array = readLine()!.split(separator: " ").map { return String($0) }

print(sequentialSearch(n: n, target: target, array: array))

バイナリナビゲーション

使用するアルゴリズムは、アレイ内のデータをソートする必要があります.
ブラウズ範囲を半分に縮小し、データのブラウズが速い.
始点、終点、中点の3つの変数を使用します.
検索するデータと中点位置のデータを繰り返し比較します.
時間的複雑度はO(logn)O(logn)O(logn)O(logn)O(logn)であり,各検査の要素数が半分に減少したためである.
そのため、データが1000万個を超える場合は、考えてみましょう.

関数

の再使用

func binarySearch(array: [Int], target: Int, start: Int, end: Int) -> Int? {
    if start > end {
        return nil
    }
    let mid = (start + end) / 2
    if array[mid] == target {
        return mid
    } else if array[mid] > target {
        return binarySearch(array: array, target: target, start: start, end: mid - 1)
    } else {
        return binarySearch(array: array, target: target, start: mid + 1, end: end)
    }
}

let inputs = readLine()!.split(separator: " ").map { return Int($0)! }
let n = inputs[0], target = inputs[1]
let array = readLine()!.split(separator: " ").map { return Int($0)! }

if let result = binarySearch(array: array, target: target, start: 0, end: n - 1) {
    print(result + 1)
} else {
    print("원소가 존재하지 않습니다")
}

反復文

を使用

func binarySearch(array: [Int], target: Int, start: Int, end: Int) -> Int? {
    var start = start, end = end
    while start <= end {
        let mid = (start + end) / 2
        if array[mid] == target {
            return mid
        } else if array[mid] > target {
            end = mid - 1
        } else {
            start = mid + 1
        }
    }
    return nil
}

let inputs = readLine()!.split(separator: " ").map { return Int($0)! }
let n = inputs[0], target = inputs[1]
let array = readLine()!.split(separator: " ").map { return Int($0)! }

if let result = binarySearch(array: array, target: target, start: 0, end: n - 1) {
    print(result + 1)
} else {
    print("원소가 존재하지 않습니다")
}

バイナリ検索問題の入力データは多く(1000万個を超える)、または検索範囲の大きさは1000億を超える.
→swift I/O受信時にタイムアウトする可能性がありますㅠ
pythonの場合、sysライブラリをインポートすることで高速入力が得られます.input_data = sys.stdin.readline().rstrip()