Tìm kiếm nhị phân

Tìm kiếm là hành động tìm kiếm một phần tử cụ thể trong một tập hợp các phần tử nhất định. Điều này trông tương tự như sắp xếp, nhưng thay vì thực hiện toàn bộ các phần tử, chúng tôi chỉ tìm kiếm một phần tử.

Nhìn chung có hai cách tìm kiếm phổ biến: Tìm kiếm tuyến tính và Tìm kiếm nhị phân . Cách đầu tiên là đơn giản nhất và chỉ hữu ích nếu danh sách bạn đang tìm kiếm không được sắp xếp. Bạn chỉ cần xem qua từ 0 đến độ dài của mảng và kiểm tra từng phần một nếu đó là phần tử bạn đang tìm kiếm. Vì vậy, độ phức tạp thời gian của nó là O (n).

Đây là triển khai Tìm kiếm tuyến tính trong 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

Đây là hình ảnh trực quan của thuật toán tìm kiếm nhị phân trong đó 7 là giá trị đích:

Từ Wikipedia

Hãy xem nó hoạt động như thế nào trong thực tế:

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

Đây là một triển khai lặp đi lặp lại của tìm kiếm nhị phân trong 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
}

Cuối cùng, bạn có thể sử dụng nó như sau:

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

Độ phức tạp về thời gian của thuật toán tìm kiếm nhị phân (trong cả hai cách tiếp cận) là O (log n) vì thời gian chạy tăng tỷ lệ với logarit của kích thước đầu vào. Độ phức tạp thời gian trong trường hợp tốt nhất sẽ là O (1) khi chỉ mục trung tâm sẽ khớp trực tiếp với giá trị mong muốn.

Độ phức tạp không gian trong phép lặp là O (1) . Trong khi ở phương pháp đệ quy, Độ phức tạp không gian là O (log n) .

Cảm ơn bạn đã dành thời gian đọc bài viết này.

Suggested posts

“Hòn đảo nhỏ đó thay đổi mọi thứ”

Cách chúng tôi thiết kế Hoạt động trực tiếp trên Lyft để nâng cao trải nghiệm của người lái

“Hòn đảo nhỏ đó thay đổi mọi thứ”

Yếu tố thay đổi cuộc chơi cho hoạt động đi chung xe Trong tất cả những việc chúng tôi làm tại Lyft, dàn dựng các cuộc đón giữa người lái và người lái xe là một trong những việc phức tạp và quan trọng nhất. Việc hoàn thành vũ đạo này phụ thuộc vào việc Lyft làm tốt nhiều thứ nhưng chỉ đơn giản là giữ cho các tay đua bắt kịp tốc độ là điều cần thiết.

Vòng đời ứng dụng

Vòng đời ứng dụng

: Chu kỳ từ khởi chạy ứng dụng đến tắt máy: Khả năng sử dụng bằng cách quản lý bộ nhớ hoặc dữ liệu ⬆️ Bảo mật có thể được xử lý UIApplication, AppDelegate Tình huống:Xác định các chức năng mà đối tượng AppDelegate nhận thông điệp được gửi từ đối tượng UIApplication và thực thi từng Not Running: Trạng thái ứng dụng không chạyKhông hoạt động: Trạng thái nơi ứng dụng đang chạy nhưng không nhận được sự kiện nàoHoạt động: Trạng thái nơi ứng dụng đang chạy và một sự kiện xảy raNền: Trạng thái nơi ứng dụng ở chế độ nền nhưng mã đang được thực thiBị treo: Trạng thái nơi ứng dụng ở chế độ nền chạy nền và không chạy mã để làm chức năng ủy quyền trong tệp AppDelegate.swift SceneDelegate Để đáp ứng tốt chức năng nhiều cảnh được hỗ trợ từ iOS 13 trở đi AppDelegate / SceneDelegate AppDelegate 1.

Related posts

Màn Đơn Ca Của Cô Gái Tóc Đỏ

Theo sự phân công của Hayden, Katie tự quay phim thủ dâm.

Màn Đơn Ca Của Cô Gái Tóc Đỏ

Sau nửa đêm, Hayden lái xe chở Katie trở lại ký túc xá đại học của cô ấy sau buổi tối bên nhau. Cô có một lớp học sớm vào buổi sáng và không có quần áo để thay sau khi ở lại với anh ta đêm hôm trước.

Theo Dõi Bất Cứ Ai Chỉ Bằng Số Điện Thoại | Điều tra OSINT

Theo Dõi Bất Cứ Ai Chỉ Bằng Số Điện Thoại | Điều tra OSINT

Bạn có thể là Điều tra viên OSINT, Người chơi CTF hoặc đơn giản là người nhận được các cuộc gọi spam. Ai đó đang cố xác minh số bạn đã thấy trong quảng cáo.

đại từ là siêu đáng sợ

Nó đập vào mắt tôi Đột ngột như nó thường xảy ra Nó lại ở giữa chừng <Không, không phải cái ở Thái Bình Dương đâu bạn màu hạt dẻ, cái ở lễ hội hóa trang> Mọi tiêu đề đều ầm ĩ…..

Cuộc đàn áp các Kitô hữu: Tội ác thù hận mà chúng ta không nói đến

Quên bài Hồi giáo đi: Cơ đốc nhân (và người Do Thái) là nạn nhân chính của tội ác căm thù tôn giáo.

Cuộc đàn áp các Kitô hữu: Tội ác thù hận mà chúng ta không nói đến

Bất kỳ lý trí nào cũng biết rằng giới chính trị và truyền thông bị chi phối bởi cánh tả, thậm chí là cực tả, một tình trạng tạo ra sự mất cân bằng trong diễn ngôn chính trị. Trong lĩnh vực tôn giáo, sự mất cân bằng này có thể thấy rõ ràng: các tờ báo và mạng lưới cánh tả không vội vàng bảo vệ đức tin Cơ đốc.