Ikili arama

Bu eğitimde İkili Arama sıralamasının nasıl çalıştığını öğreneceksiniz. Ayrıca, C, C ++, Java ve Python'da İkili Arama'nın çalışan örneklerini bulacaksınız.

İkili Arama, sıralı bir dizide bir elemanın konumunu bulmak için kullanılan bir arama algoritmasıdır.

Bu yaklaşımda, eleman her zaman bir dizinin bir bölümünün ortasında aranır.

İkili arama yalnızca sıralı bir öğe listesine uygulanabilir. Öğeler zaten sıralanmamışsa, önce onları sıralamamız gerekir.

İkili Arama Çalışması

İkili Arama Algoritması aşağıda tartışılan iki şekilde uygulanabilir.

  1. Yinelemeli Yöntem
  2. Özyinelemeli Yöntem

Yinelemeli yöntem, böl ve yönet yaklaşımını izler.

Her iki yöntem için genel adımlar aşağıda tartışılmaktadır.

  1. Aramanın gerçekleştirileceği dizi şöyledir: İlk dizi
    Aranacak x = 4öğe olsun .
  2. Sırasıyla en düşük ve en yüksek konumlarda düşük ve yüksek iki işaretçi ayarlayın. İşaretçileri ayarlama
  3. Yani dizinin ortasındaki orta elemanı bulun. (arr(low + high)) / 2 = 6. Orta eleman
  4. Eğer x == mid ise, mid.Else dönün, aranacak elemanı m ile karşılaştırın.
  5. Eğer x> mid, x'i ortanın sağ tarafındaki elemanların orta elemanıyla karşılaştırın. Bu, düşük olarak ayarlanarak yapılır low = mid + 1.
  6. Aksi takdirde, x'i ortanın sol tarafındaki öğelerin orta öğesiyle karşılaştırın. Bu, yüksek olarak ayarlanarak yapılır high = mid - 1. Orta elemanı bulmak
  7. Düşük yüksek ile buluşana kadar 3 ila 6. adımları tekrarlayın. Orta eleman
  8. x = 4bulunan. Bulundu

İkili Arama Algoritması

Yineleme Yöntemi

alçak ve yüksek işaretçiler birbirleriyle buluşana kadar yapın. orta = (düşük + yüksek) / 2 if (x == arr (orta)) ortada dön if (x> A (orta)) // x sağ tarafta düşük = orta + 1 değilse // x açık sol taraf yüksek = orta - 1

Özyinelemeli Yöntem

 binarySearch (arr, x, low, high) eğer düşükse> yüksek getiri False else mid = (low + high) / 2 eğer x == arr (mid) eğer x <data (mid) // x ise sağ tarafa dönüş binarySearch (arr, x, mid + 1, high) else // x sağ tarafta return binarySearch (arr, x, low, mid - 1)

Python, Java, C / C ++ Örnekleri (Yinelemeli Yöntem)

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

Python, Java, C / C ++ Örnekleri (Özyinelemeli Yöntem)

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

İkili Arama Karmaşıklığı

Zaman Karmaşıklıkları

  • En iyi durum karmaşıklığı :O(1)
  • Ortalama vaka karmaşıklığı :O(log n)
  • En kötü durum karmaşıklığı :O(log n)

Uzay Karmaşıklığı

İkili aramanın uzay karmaşıklığı O(n).

İkili Arama Uygulamaları

  • Java, .Net, C ++ STL kütüphanelerinde
  • Hata ayıklama sırasında, ikili arama, hatanın meydana geldiği yeri belirlemek için kullanılır.

Ilginç makaleler...