Pencarian Biner

Dalam tutorial ini, Anda akan mempelajari cara kerja jenis Pencarian Biner. Selain itu, Anda akan menemukan contoh kerja Pencarian Biner dalam C, C ++, Java dan Python.

Pencarian Biner adalah algoritma pencarian untuk menemukan posisi elemen dalam array yang diurutkan.

Dalam pendekatan ini, elemen selalu dicari di tengah porsi array.

Pencarian biner hanya dapat diterapkan pada daftar item yang diurutkan. Jika elemen belum diurutkan, kita perlu mengurutkannya terlebih dahulu.

Pencarian Biner Bekerja

Algoritma Pencarian Biner dapat diimplementasikan dalam dua cara yang dibahas di bawah ini.

  1. Metode Iteratif
  2. Metode Rekursif

Metode rekursif mengikuti pendekatan divide and conquer.

Langkah-langkah umum untuk kedua metode dibahas di bawah ini.

  1. Larik di mana pencarian akan dilakukan adalah: Array awal
    Membiarkan x = 4menjadi elemen yang akan dicari.
  2. Tetapkan dua petunjuk rendah dan tinggi di posisi terendah dan tertinggi masing-masing. Menetapkan petunjuk
  3. Temukan elemen tengah di tengah larik yaitu. (arr(low + high)) / 2 = 6. Elemen tengah
  4. Jika x == mid, kemudian kembalikan mid.Else, bandingkan elemen yang akan dicari dengan m.
  5. Jika x> mid, bandingkan x dengan elemen tengah dari elemen di sisi kanan tengah. Ini dilakukan dengan menyetel rendah ke low = mid + 1.
  6. Lain, bandingkan x dengan elemen tengah elemen di sisi kiri tengah. Ini dilakukan dengan menetapkan tinggi ke high = mid - 1. Menemukan elemen tengah
  7. Ulangi langkah 3 hingga 6 sampai rendah bertemu tinggi. Elemen tengah
  8. x = 4ditemukan. Ditemukan

Algoritma Pencarian Biner

Metode Iterasi

lakukan sampai petunjuk rendah dan tinggi bertemu satu sama lain. mid = (low + high) / 2 if (x == arr (mid)) return mid else if (x> A (mid)) // x ada di sisi kanan low = mid + 1 else // x aktif tinggi sisi kiri = pertengahan - 1

Metode Rekursif

 binarySearch (arr, x, low, high) if low> high return False else mid = (low + high) / 2 if x == arr (mid) return mid else jika x <data (mid) // x ada di sisi kanan return binarySearch (arr, x, mid + 1, high) else // x ada di sisi kanan return binarySearch (arr, x, low, mid - 1)

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

Python Java 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 ++ (Metode Rekursif)

Python Java 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); )

Kompleksitas Pencarian Biner

Kompleksitas Waktu

  • Kompleksitas kasus terbaik :O(1)
  • Kompleksitas kasus rata-rata :O(log n)
  • Kompleksitas kasus terburuk :O(log n)

Kompleksitas Ruang

Kompleksitas ruang dari pencarian biner adalah O(n).

Aplikasi Pencarian Biner

  • Di perpustakaan Java, .Net, C ++ STL
  • Saat melakukan debug, pencarian biner digunakan untuk menunjukkan tempat terjadinya kesalahan.

Artikel yang menarik...

Direkomendasikan