binary search algorithm java implementation examples
Bu Öğretici, Algoritma, Uygulama ve Java İkili Arama Kodu Örnekleri ile birlikte Java'da İkili Arama ve Yinelemeli İkili Aramayı Açıklayacaktır:
Java'da ikili arama, bir koleksiyonda hedeflenen bir değeri veya anahtarı aramak için kullanılan bir tekniktir. Bir anahtar aramak için 'böl ve yönet' tekniğini kullanan bir tekniktir.
Bir anahtarı aramak için İkili aramanın uygulanacağı koleksiyon, artan sırada sıralanmalıdır.
Genellikle, programlama dillerinin çoğu, koleksiyonda veri aramak için kullanılan Doğrusal arama, İkili arama ve Karma tekniklerini destekler. Sonraki eğitimlerimizde hash yapmayı öğreneceğiz.
=> Java'yı Sıfırdan Öğrenmek İçin Burayı Ziyaret Edin.
Ne öğreneceksin:
Java'da İkili Arama
Doğrusal arama temel bir tekniktir. Bu teknikte, dizi sırayla gezilir ve anahtar bulunana veya dizinin sonuna ulaşılana kadar her öğe anahtarla karşılaştırılır.
Doğrusal arama, pratik uygulamalarda nadiren kullanılır. İkili arama, doğrusal aramadan çok daha hızlı olduğu için en sık kullanılan tekniktir.
Java, ikili arama yapmak için üç yol sağlar:
en iyi sürücü klonlama yazılımı Windows 10
- Yinelemeli yaklaşımı kullanma
- Özyinelemeli bir yaklaşım kullanma
- Arrays.binarySearch () yöntemini kullanma.
Bu eğitimde, tüm bu 3 yöntemi uygulayacak ve tartışacağız.
Java'da İkili Arama Algoritması
İkili arama yönteminde, koleksiyon tekrar tekrar ikiye bölünür ve anahtar öğe, koleksiyonun orta öğesinden küçük veya büyük olmasına bağlı olarak koleksiyonun sol veya sağ yarısında aranır.
Basit bir İkili Arama Algoritması aşağıdaki gibidir:
- Koleksiyonun orta elemanını hesaplayın.
- Anahtar öğeleri orta öğe ile karşılaştırın.
- Anahtar = orta eleman ise, bulunan anahtar için orta dizin konumunu döndürürüz.
- Aksi takdirde anahtar> orta öğe ise, anahtar koleksiyonun sağ yarısında bulunur. Bu nedenle, koleksiyonun alt (sağ) yarısında 1'den 3'e kadar olan adımları tekrarlayın.
- Başka anahtar
Yukarıdaki adımlardan da görebileceğiniz gibi, İkili aramada, koleksiyondaki öğelerin yarısı ilk karşılaştırmanın hemen ardından göz ardı edilir.
Aynı adım dizisinin yinelemeli ve yinelemeli ikili arama için de geçerli olduğuna dikkat edin.
Bir örnek kullanarak ikili arama algoritmasını gösterelim.
Örneğinaşağıdaki sıralı 10 eleman dizisini alın.
Dizinin orta konumunu hesaplayalım.
Orta = 0 + 9/2 = 4
# 1) Anahtar = 21
İlk olarak, anahtar değerini (mid) öğesiyle karşılaştıracağız ve ortadaki öğe değerinin = 21 olduğunu bulacağız.
Böylece o anahtarı = (mid) buluruz. Dolayısıyla anahtar, dizideki 4. konumda bulunur.
# 2) Anahtar = 25
Önce anahtar değerini mid ile karşılaştırıyoruz. Gibi (21<25), we will directly search for the key in the upper half of the array.
Şimdi yine dizinin üst yarısının ortasını bulacağız.
Orta = 4 + 9/2 = 6
Konumdaki değer (orta) = 25
Şimdi anahtar unsuru orta unsurla karşılaştırıyoruz. Yani (25 == 25), dolayısıyla anahtarı (mid) = 6 konumunda bulduk.
Böylece diziyi tekrar tekrar böleriz ve anahtar elemanı orta ile karşılaştırarak anahtarı hangi yarıda arayacağımıza karar veririz. İkili arama, zaman ve doğruluk açısından daha verimlidir ve çok daha hızlıdır.
İkili Arama Uygulama Java
Yukarıdaki algoritmayı kullanarak, yinelemeli yaklaşımı kullanarak Java'da bir İkili arama programı uygulayalım. Bu programda örnek bir dizi alıyoruz ve bu dizi üzerinde ikili arama yapıyoruz.
import java.util.*; class Main{ public static void main(String args()){ int numArray() = {5,10,15,20,25,30,35}; System.out.println('The input array: ' + Arrays.toString(numArray)); //key to be searched int key = 20; System.out.println('
Key to be searched=' + key); //set first to first index int first = 0; //set last to last elements in array int last=numArray.length-1; //calculate mid of the array int mid = (first + last)/2; //while first and last do not overlap while( first <= last ){ //if the mid < key, then key to be searched is in the first half of array if ( numArray(mid) last ){ System.out.println('Element is not found!'); } } } Çıktı:
Giriş dizisi: (5, 10, 15, 20, 25, 30, 35)
Aranacak anahtar = 20
Öğe, dizin: 3'te bulunur
Yukarıdaki program İkili aramanın yinelemeli bir yaklaşımını göstermektedir. Başlangıçta bir dizi bildirilir, ardından aranacak bir anahtar tanımlanır.
Dizinin ortasını hesapladıktan sonra, anahtar orta elemanla karşılaştırılır. Ardından, anahtarın anahtardan küçük veya büyük olmasına bağlı olarak, anahtar sırasıyla dizinin alt veya üst yarısında aranır.
Java'da Yinelemeli İkili Arama
Özyineleme tekniğini kullanarak ikili arama da gerçekleştirebilirsiniz. Burada, ikili arama yöntemi, anahtar bulunana veya tüm liste tükenene kadar özyinelemeli olarak çağrılır.
Yinelemeli ikili arama uygulayan program aşağıda verilmiştir:
en iyi sanal gerçeklik uygulamaları nelerdir
import java.util.*; class Main{ //recursive method for binary search public static int binary_Search(int intArray(), int low, int high, int key){ //if array is in order then perform binary search on the array if (high>=low){ //calculate mid int mid = low + (high - low)/2; //if key =intArray(mid) return mid if (intArray(mid) == key){ return mid; } //if intArray(mid) > key then key is in left half of array if (intArray(mid) > key){ return binary_Search(intArray, low, mid-1, key);//recursively search for key }else //key is in right half of the array { return binary_Search(intArray, mid+1, high, key);//recursively search for key } } return -1; } public static void main(String args()){ //define array and key int intArray() = {1,11,21,31,41,51,61,71,81,91}; System.out.println('Input List: ' + Arrays.toString(intArray)); int key = 31; System.out.println('
The key to be searched:' + key); int high=intArray.length-1; //call binary search method int result = binary_Search(intArray,0,high,key); //print the result if (result == -1) System.out.println('
Key not found in given list!'); else System.out.println('
Key is found at location: '+result + ' in the list'); } } Çıktı:
Giriş Listesi: (1, 11, 21, 31, 41, 51, 61, 71, 81, 91
Aranacak anahtar:
Anahtar şu konumda bulunur: listede 3
Arrays.binarySearch () yöntemini kullanma.
Java'daki Arrays sınıfı, verilen Array üzerinde ikili aramayı gerçekleştiren bir 'binarySearch ()' yöntemi sağlar. Bu yöntem, aranacak diziyi ve anahtarı argüman olarak alır ve dizideki anahtarın konumunu döndürür. Anahtar bulunmazsa, yöntem -1'i döndürür.
Aşağıdaki örnek, Arrays.binarySearch () yöntemini uygular.
import java.util.Arrays; class Main{ public static void main(String args()){ //define an array int intArray() = {10,20,30,40,50,60,70,80,90}; System.out.println('The input Array : ' + Arrays.toString(intArray)); //define the key to be searched int key = 50; System.out.println('
The key to be searched:' + key); //call binarySearch method on the given array with key to be searched int result = Arrays.binarySearch(intArray,key); //print the return result if (result <0) System.out.println('
Key is not found in the array!'); else System.out.println('
Key is found at index: '+result + ' in the array.'); } } Çıktı:
Giriş Dizisi: (10, 20, 30, 40, 50, 60, 70, 80, 90)
Aranacak anahtar: 50
Anahtar, dizide dizin: 4'te bulunur.
Sıkça Sorulan Sorular
S # 1) İkili aramayı nasıl yazarsınız?
Cevap: İkili arama genellikle diziyi ikiye bölerek yapılır. Aranacak anahtar orta elemandan daha büyükse, anahtar bulunana kadar alt diziyi daha fazla bölerek ve araştırarak dizinin üst yarısı aranır.
Benzer şekilde, anahtar orta öğeden küçükse, dizinin alt yarısında anahtar aranır.
S # 2) İkili arama nerede kullanılır?
bir xml dosyasını nasıl açarsın
Cevap: İkili arama, özellikle bellek alanı kompakt ve sınırlı olduğunda yazılım uygulamalarında sıralı bir veriyi aramak için kullanılır.
S # 3) İkili aramanın büyük O değeri nedir?
Cevap: İkili aramanın zaman karmaşıklığı O (logn) olup, burada n, dizideki elemanların sayısıdır. İkili aramanın uzay karmaşıklığı O (1) 'dir.
S # 4) İkili arama yinelemeli mi?
Cevap: Evet. İkili arama, böl ve yönet stratejisinin bir örneği olduğundan ve özyineleme kullanılarak uygulanabilir. Diziyi ikiye bölebilir ve aynı yöntemi tekrar tekrar ikili aramayı gerçekleştirmek için çağırabiliriz.
S # 5) Neden buna ikili arama deniyor?
Cevap: İkili arama algoritması, diziyi art arda yarıya veya iki parçaya bölen bir böl ve yönet stratejisi kullanır. Bu nedenle ikili arama olarak adlandırılır.
Sonuç
İkili arama, Java'da sıklıkla kullanılan arama tekniğidir. İkili aramanın gerçekleştirilmesi için gereken, verilerin artan sırada sıralanması gerektiğidir.
İkili arama, yinelemeli veya özyinelemeli bir yaklaşım kullanılarak gerçekleştirilebilir. Java'daki Arrays sınıfı, bir Array üzerinde ikili arama gerçekleştiren 'binarySearch' yöntemini de sağlar.
Sonraki eğitimlerimizde, Java'da çeşitli Sıralama Tekniklerini keşfedeceğiz.
=> Basit Java Eğitim Serisine Buradan Dikkat Edin.
Önerilen Kaynaklar
- Java'da Seçim Sırala - Algoritmayı ve Örnekleri Sıralama Seçimi
- Java'da Ekleme Sıralama - Ekleme Sıralama Algoritması ve Örnekler
- İkili Arama Ağacı C ++: Örneklerle BST Uygulaması ve İşlemleri
- Java Arayüzü ve Örneklerle Soyut Sınıf Eğitimi
- Yeni Başlayanlar İçin JAVA Eğitimi: 100+ Uygulamalı Java Video Eğitimi
- Java'da Kabarcık Sıralama - Java Sıralama Algoritmaları ve Kod Örnekleri
- Java Dize Eğitimi | Örneklerle Java Dize Yöntemleri
- Java Vektör Nedir | Örneklerle Java Vektör Sınıfı Eğitimi