Pencarian Perduaan

Dalam tutorial ini, anda akan belajar bagaimana kaedah Carian Binari berfungsi. Anda juga akan dapati contoh carian Binary di C, C ++, Java dan Python.

Binary Search adalah algoritma carian untuk mencari kedudukan elemen dalam susunan yang disusun.

Dalam pendekatan ini, elemen selalu dicari di tengah-tengah bahagian array.

Pencarian binari dapat dilaksanakan hanya pada senarai item yang disusun. Sekiranya elemen belum disusun, kita perlu menyusunnya terlebih dahulu.

Pencarian Perduaan Berfungsi

Algoritma Pencarian Binari dapat dilaksanakan dengan dua cara yang dibincangkan di bawah.

  1. Kaedah berulang
  2. Kaedah Rekursif

Kaedah rekursif mengikuti pendekatan membahagi dan menakluki.

Langkah-langkah umum untuk kedua kaedah dibincangkan di bawah.

  1. Array di mana pencarian harus dilakukan adalah: array awal
    Biarkan x = 4menjadi elemen yang akan dicari.
  2. Tetapkan dua titik rendah dan tinggi masing-masing pada kedudukan terendah dan tertinggi. Menetapkan petunjuk
  3. Cari elemen tengah pertengahan array iaitu. (arr(low + high)) / 2 = 6. Elemen pertengahan
  4. Sekiranya x == pertengahan, kemudian kembali pertengahan. Lain, bandingkan elemen yang akan dicari dengan m.
  5. Jika x> mid, bandingkan x dengan elemen tengah elemen di sebelah kanan pertengahan. Ini dilakukan dengan menetapkan rendah ke low = mid + 1.
  6. Lain, bandingkan x dengan elemen tengah elemen di sebelah kiri tengah. Ini dilakukan dengan menetapkan tinggi ke high = mid - 1. Mencari elemen pertengahan
  7. Ulangi langkah 3 hingga 6 sehingga rendah memenuhi tinggi. Elemen pertengahan
  8. x = 4dijumpai. Dijumpai

Algoritma Pencarian Perduaan

Kaedah Pengulangan

lakukan sehingga titik rendah dan tinggi saling bertemu. pertengahan = (rendah + tinggi) / 2 jika (x == arr (tengah)) kembali ke pertengahan jika (x> A (pertengahan)) // x berada di sebelah kanan rendah = pertengahan + 1 yang lain // x dihidupkan sebelah kiri tinggi = pertengahan - 1

Kaedah Rekursif

 binarySearch (arr, x, low, high) if low> high return False else mid = (rendah + tinggi) / 2 jika x == arr (tengah) kembali pertengahan jika x <data (pertengahan) // x berada di binary binary return kanan (arr, x, pertengahan + 1, tinggi) yang lain // x ada di sebelah kanan return binary binary (arr, x, low, mid - 1)

Contoh Python, Java, C / C ++ (Kaedah Iteratif)

Python Java C C ++ 
 # Binary Search in python def binarySearch(array, x, low, high): # Repeat until the pointers low and high meet each other while low <= high: mid = low + (high - low)//2 if array(mid) == x: return mid elif array(mid) < x: low = mid + 1 else: high = mid - 1 return -1 array = (3, 4, 5, 6, 7, 8, 9) x = 4 result = binarySearch(array, x, 0, len(array)-1) if result != -1: print("Element is present at index " + str(result)) else: print("Not found")
 // Binary Search in Java class BinarySearch ( int binarySearch(int array(), int x, int low, int high) ( // Repeat until the pointers low and high meet each other while (low <= high) ( int mid = low + (high - low) / 2; if (array(mid) == x) return mid; if (array(mid) < x) low = mid + 1; else high = mid - 1; ) return -1; ) public static void main(String args()) ( BinarySearch ob = new BinarySearch(); int array() = ( 3, 4, 5, 6, 7, 8, 9 ); int n = array.length; int x = 4; int result = ob.binarySearch(array, x, 0, n - 1); if (result == -1) System.out.println("Not found"); else System.out.println("Element found at index " + result); ) )
 // Binary Search in C #include int binarySearch(int array(), int x, int low, int high) ( // Repeat until the pointers low and high meet each other while (low <= high) ( int mid = low + (high - low) / 2; if (array(mid) == x) return mid; if (array(mid) < x) low = mid + 1; else high = mid - 1; ) return -1; ) int main(void) ( int array() = (3, 4, 5, 6, 7, 8, 9); int n = sizeof(array) / sizeof(array(0)); int x = 4; int result = binarySearch(array, x, 0, n - 1); if (result == -1) printf("Not found"); else printf("Element is found at index %d", result); return 0; )
 // Binary Search in C++ #include using namespace std; int binarySearch(int array(), int x, int low, int high) ( // Repeat until the pointers low and high meet each other while (low <= high) ( int mid = low + (high - low) / 2; if (array(mid) == x) return mid; if (array(mid) < x) low = mid + 1; else high = mid - 1; ) return -1; ) int main(void) ( int array() = (3, 4, 5, 6, 7, 8, 9); int x = 4; int n = sizeof(array) / sizeof(array(0)); int result = binarySearch(array, x, 0, n - 1); if (result == -1) printf("Not found"); else printf("Element is found at index %d", result); )

Contoh Python, Java, C / C ++ (Kaedah Rekursif)

Python Java C C ++ 
 # Binary Search in python def binarySearch(array, x, low, high): if high>= low: mid = low + (high - low)//2 # If found at mid, then return it if array(mid) == x: return mid # Search the left half elif array(mid)> x: return binarySearch(array, x, low, mid-1) # Search the right half else: return binarySearch(array, x, mid + 1, high) else: return -1 array = (3, 4, 5, 6, 7, 8, 9) x = 4 result = binarySearch(array, x, 0, len(array)-1) if result != -1: print("Element is present at index " + str(result)) else: print("Not found")
 // Binary Search in Java class BinarySearch ( int binarySearch(int array(), int x, int low, int high) ( if (high>= low) ( int mid = low + (high - low) / 2; // If found at mid, then return it if (array(mid) == x) return mid; // Search the left half if (array(mid)> x) return binarySearch(array, x, low, mid - 1); // Search the right half return binarySearch(array, x, mid + 1, high); ) return -1; ) public static void main(String args()) ( BinarySearch ob = new BinarySearch(); int array() = ( 3, 4, 5, 6, 7, 8, 9 ); int n = array.length; int x = 4; int result = ob.binarySearch(array, x, 0, n - 1); if (result == -1) System.out.println("Not found"); else System.out.println("Element found at index " + result); ) )
 // Binary Search in C #include int binarySearch(int array(), int x, int low, int high) ( if (high>= low) ( int mid = low + (high - low) / 2; // If found at mid, then return it if (array(mid) == x) return mid; // Search the left half if (array(mid)> x) return binarySearch(array, x, low, mid - 1); // Search the right half return binarySearch(array, x, mid + 1, high); ) return -1; ) int main(void) ( int array() = (3, 4, 5, 6, 7, 8, 9); int n = sizeof(array) / sizeof(array(0)); int x = 4; int result = binarySearch(array, x, 0, n - 1); if (result == -1) printf("Not found"); else printf("Element is found at index %d", result); )
 // Binary Search in C++ #include using namespace std; int binarySearch(int array(), int x, int low, int high) ( if (high>= low) ( int mid = low + (high - low) / 2; // If found at mid, then return it if (array(mid) == x) return mid; // Search the left half if (array(mid)> x) return binarySearch(array, x, low, mid - 1); // Search the right half return binarySearch(array, x, mid + 1, high); ) return -1; ) int main(void) ( int array() = (3, 4, 5, 6, 7, 8, 9); int x = 4; int n = sizeof(array) / sizeof(array(0)); int result = binarySearch(array, x, 0, n - 1); if (result == -1) printf("Not found"); else printf("Element is found at index %d", result); )

Kerumitan Pencarian Binari

Kerumitan Masa

  • Kerumitan kes terbaik :O(1)
  • Kerumitan kes purata :O(log n)
  • Kerumitan kes terburuk :O(log n)

Kerumitan Ruang

Kerumitan ruang carian binari adalah O(n).

Aplikasi Carian Binari

  • Di perpustakaan Java, .Net, C ++ STL
  • Semasa melakukan debug, carian binari digunakan untuk menentukan tempat di mana kesalahan berlaku.

Artikel menarik...