Carian Binari || Python || Struktur dan Algoritma Data

Carian Binari

Carian Binari ialah algoritma yang berulang kali membahagikan ruang carian kepada separuh. Teknik pencarian ini mengikut strategi bahagi dan takluk. Ruang carian sentiasa berkurangan kepada separuh dalam setiap lelaran.mengakibatkan kerumitan masa O(log(n)), dengan n ialah bilangan elemen.

Keadaan: Tatasusunan harus diisih tetapi ia juga boleh digunakan pada fungsi monoton di mana kita perlu mencari peningkatan atau penurunan secara monoton.

Ia berfungsi apabila kita perlu mengecilkan ruang carian dalam masa logaritma.

Kami menggunakan dua penunjuk, kiri dan kanan. Ambil purata kiri dan kanan untuk mencari elemen pertengahan.

Sekarang, kami menyemak ke mana kami harus mengalihkan penunjuk kiri dan kanan kami berdasarkan syarat.

Terutamanya, tiga langkah diperlukan untuk menyelesaikan masalah:

1. Pra-pemprosesan: Isih input jika ia tidak diisih.
2. Carian Perduaan: Gunakan dua penunjuk dan cari pertengahan untuk membahagikan ruang carian, kemudian pilih separuh yang betul dengan sewajarnya.
3. Pasca pemprosesan: Tentukan output.

Kelebihan Algoritma Carian Binari - Carian binari lebih pantas daripada carian linear untuk data besar kerana ia memotong tatasusunan pada separuh setiap kali, bukannya menyemak setiap elemen satu demi satu. Ini menjadikannya lebih cepat dan lebih cekap.

Keterbatasan: Carian binari hanya berfungsi pada tatasusunan yang diisih, jadi ia tidak cekap untuk tatasusunan kecil yang tidak diisih kerana pengisihan mengambil masa tambahan. Ia juga tidak berfungsi sebaik carian linear untuk carian kecil dalam memori.

Aplikasi: Ia digunakan untuk mencari elemen dalam tatasusunan diisih dengan kerumitan masa O(log(n)) dan ia juga boleh digunakan untuk mencari elemen terkecil atau terbesar dalam tatasusunan.

Kod Carian Binari Asas -

Kod

def binarySearch(nums, target):
    if len(nums) == 0:
        return -1

    left, right = 0, len(nums) - 1

    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    # End Condition: left > right
    return -1

33. Cari dalam Tatasusunan Isih Diputar
Memandangkan nombor tatasusunan selepas putaran yang mungkin dan sasaran integer, kembalikan indeks sasaran jika ia dalam angka, atau -1 jika ia bukan dalam nombor.
Anda mesti menulis algoritma dengan kerumitan masa jalan O(log n).
Contoh 1:
Input: angka = [4,5,6,7,0,1,2], sasaran = 0
Keluaran: 4

Contoh 2:
Input: angka = [4,5,6,7,0,1,2], sasaran = 3
Output: -1

Contoh 3:
Input: angka = [1], sasaran = 0
Output: -1

Kod

def binarySearch(nums, target):
    if len(nums) == 0:
        return -1

    left, right = 0, len(nums) - 1

    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    # End Condition: left > right
    return -1

1. Gunakan dua penunjuk, kiri dan kanan, dan ulangi sehingga ia bertindih.
2. Cari elemen pertengahan.
3. Memandangkan tatasusunan diisih tetapi diputar, kita tidak boleh membandingkan unsur kiri atau kanan dengan pertengahan.
4. Mula-mula, tentukan bahagian kiri atau kanan yang diisih dengan membandingkan penunjuk tengah dengan penunjuk kiri atau kanan.
5. Berdasarkan kesimpulan ini, laraskan penunjuk dengan sewajarnya.

Kerumitan Masa - O(log(n)) kerana ruang carian semakin dibahagikan kepada separuh dalam setiap lelaran.
Kerumitan Angkasa Lepas - O(1)

Meningkat secara Monoton

162. Cari Elemen Puncak

Unsur puncak ialah unsur yang lebih besar daripada jirannya.
Memandangkan nombor tatasusunan integer terindeks 0, cari elemen puncak dan kembalikan indeksnya. Jika tatasusunan mengandungi berbilang puncak, kembalikan indeks kepada mana-mana puncak.
Anda mungkin membayangkan bahawa nums[-1] = nums[n] = -∞. Dalam erti kata lain, elemen sentiasa dianggap lebih hebat daripada jiran yang berada di luar tatasusunan.
Anda mesti menulis algoritma yang berjalan dalam masa O(log n).

Contoh 1:
Input: nombor = [1,2,3,1]
Keluaran: 2
Penjelasan: 3 ialah elemen puncak dan fungsi anda harus mengembalikan nombor indeks 2.
Contoh 2:
Input: nombor = [1,2,1,3,5,6,4]
Keluaran: 5
Penjelasan: Fungsi anda boleh mengembalikan sama ada nombor indeks 1 dengan unsur puncak ialah 2 atau nombor indeks 5 dengan unsur puncak ialah 6.

Kod

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums)-1

        while left <= right:

            mid = (left + right)//2
            print(f'left is {left},right is {right} and mid is {mid}')
            if nums[mid]==target:
                return mid

            if nums[mid] >= nums[left]:
                # if nums[mid]< target and target >= nums[left]:
                if nums[left] <= target < nums[mid]:
                    right = mid -1
                else:
                    left = mid +1
            else:
                # if nums[mid] < target and target <= nums[right]:
                if nums[mid] < target <= nums[right]:
                    left = mid +1
                else:
                    right = mid - 1

        return -1

1. Dalam masalah jenis ini, kita perlu menyemak puncak dengan membandingkan elemen kiri atau kanan bahagian tengah.
2. Ini membantu menentukan sama ada graf itu arah aliran ke atas atau ke bawah.
3. Untuk mencari maksimum, cari cerun ke atas dan teroka subruang yang betul.
4. Untuk mencari minimum, cari subruang kiri

Kerumitan Masa - O(log(n)) kerana ruang carian semakin dibahagikan kepada separuh dalam setiap lelaran.
Kerumitan Angkasa Lepas - O(1)

Atas ialah kandungan terperinci Carian Binari || Python || Struktur dan Algoritma Data. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!