Pencarian Biner

Pencarian adalah tindakan mencari elemen tertentu dalam kumpulan elemen tertentu. Ini terlihat mirip dengan pengurutan, tetapi alih-alih melakukan seluruh rangkaian elemen, kami hanya mencari satu elemen.

Secara umum ada dua cara umum untuk mencari: Linear Search dan Binary Search . Yang pertama adalah yang paling sederhana, dan hanya berguna jika daftar yang Anda cari tidak diurutkan sama sekali. Anda cukup menelusuri dari 0 hingga panjang array dan memeriksa satu per satu apakah itu elemen yang Anda cari. Jadi kompleksitas waktunya adalah O(n).

Ini adalah implementasi Pencarian Linear di 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

Berikut adalah visualisasi dari algoritma pencarian biner dimana 7 adalah nilai targetnya:

Dari Wikipedia

Mari kita lihat cara kerjanya dalam praktik:

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

Berikut ini adalah implementasi berulang dari pencarian biner di 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
}

Akhirnya, Anda dapat menggunakannya seperti ini:

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

The Waktu Kompleksitas dari algoritma pencarian biner (di kedua pendekatan) adalah O (log n) sejak waktu berjalan tumbuh secara proporsional dengan logaritma dari ukuran masukan. Kompleksitas waktu kasus terbaik adalah O(1) ketika indeks pusat akan langsung cocok dengan nilai yang diinginkan.

The Ruang Kompleksitas dalam berulang adalah O (1) . Sedangkan pada metode rekursif, Kompleksitas Ruang adalah O(log n) .

Terima kasih telah meluangkan waktu untuk membaca artikel ini.

Suggested posts

“Pulau kecil itu mengubah segalanya”

Bagaimana kami merancang Lyft Live Activities untuk meningkatkan pengalaman pengendara

“Pulau kecil itu mengubah segalanya”

Pengubah permainan untuk rideshare Dari semua hal yang kami lakukan di Lyft, membuat koreografi pickup antara pengendara & pengemudi adalah salah satu yang paling kompleks dan konsekuensial. Memakukan koreografi ini bergantung pada Lyft yang melakukan banyak hal dengan baik, tetapi menjaga kecepatan pengendara itu penting.

Siklus Hidup Aplikasi

Siklus Hidup Aplikasi

: Siklus dari peluncuran aplikasi ke shutdown: Kegunaan dengan mengelola memori atau data ⬆️ Keamanan dapat diproses UIApplication, situasi AppDelegate: Menentukan fungsi yang diterima objek AppDelegate pesan yang dikirim dari objek UIApplication dan mengeksekusi setiap Tidak Berjalan: Status saat aplikasi tidak berjalanTidak aktif: Status saat aplikasi berjalan tetapi tidak ada peristiwa yang diterimaAktif: Status saat aplikasi berjalan dan peristiwa terjadiLatar belakang: Status saat aplikasi berada di latar belakang tetapi kode yang sedang dieksekusiDitangguhkan: Status saat aplikasi berada di latar belakang dan menjalankan tidak ada kode untuk menjadi fungsi delegasi dalam file AppDelegate.swift SceneDelegate Untuk merespons dengan baik fungsi beberapa adegan yang didukung dari iOS 13 dan seterusnya AppDelegate / SceneDelegate AppDelegate 1.

Related posts

Dua tahun dalam desain- Yang baik, buruk, dan jelek…

Dua tahun dalam desain- Yang baik, buruk, dan jelek…

“Hai Siri, mainkan Me Dive oleh Olivia Dean.” Saat itu Mei 2021 ketika saya memulai magang di Future Academy Africa di Akure, Nigeria.

Tidak ada lagi kata sandi — bagaimana kunci sandi akan menggantikan kata sandi Anda

Tidak ada lagi kata sandi — bagaimana kunci sandi akan menggantikan kata sandi Anda

Untuk menghindari ambiguitas istilah berikut akan digunakan; Pengautentikasi; Ponsel yang digunakan untuk membuat situs web login; Situs web atau aplikasi yang digunakan pengguna untuk membuat Layanan permintaan login; Vendor menyediakan layanan yang diberikan misalnya

Revolusi Tempat Kerja: Para Ahli Teratas Membahas Kerja Hibrid dan Jarak Jauh

Revolusi Tempat Kerja: Para Ahli Teratas Membahas Kerja Hibrid dan Jarak Jauh

Dalam lanskap bisnis yang berkembang pesat saat ini, konsep kerja hibrid dan jarak jauh telah mendapatkan momentum yang belum pernah terjadi sebelumnya. Saat perusahaan terus beradaptasi dengan perubahan kebutuhan dan harapan karyawan mereka, para ahli dari berbagai bidang berkumpul untuk membahas manfaat, tantangan, dan masa depan cara kerja transformatif ini.

Penampilan Solo Gadis Berambut Merah

Atas tugas dari Hayden, Katie memfilmkan dirinya sedang masturbasi.

Penampilan Solo Gadis Berambut Merah

Sudah lewat tengah malam ketika Hayden mengantar Katie kembali ke asrama kampusnya setelah malam mereka bersama. Dia memiliki kelas awal di pagi hari dan tidak memiliki pakaian ganti lagi setelah tinggal bersamanya malam sebelumnya.