Bu yazımızda İkili Arama Algoritmasını ele alacağız. Arama, listedeki belirli bir öğeyi bulma işlemidir. Öğe listede mevcutsa süreç başarılı olarak adlandırılır ve süreç o öğenin konumunu döndürür. Aksi takdirde arama başarısız olarak adlandırılır.
Doğrusal Arama ve İkili Arama iki popüler arama tekniğidir. Burada İkili Arama Algoritmasını tartışacağız.
İkili arama, sıralanmış listelerde verimli bir şekilde çalışan arama tekniğidir. Bu nedenle, ikili arama tekniğini kullanarak bir listede bir öğeyi aramak için listenin sıralandığından emin olmalıyız.
dizeye Java tamsayı
İkili arama, listenin iki yarıya bölündüğü ve öğenin listenin orta öğesiyle karşılaştırıldığı böl ve yönet yaklaşımını izler. Eğer eşleşme bulunursa ortadaki elemanın konumu döndürülür. Aksi takdirde, maç boyunca elde edilen sonuca bağlı olarak yarılardan herhangi birini araştırırız.
NOT: Sıralanmış dizi öğelerine ikili arama uygulanabilir. Liste elemanları sıralı bir şekilde düzenlenmemişse, önce onları sıralamamız gerekir.
Şimdi İkili Aramanın algoritmasını görelim.
Algoritma
Binary_Search(a, lower_bound, upper_bound, val) // 'a' is the given array, 'lower_bound' is the index of the first array element, 'upper_bound' is the index of the last array element, 'val' is the value to search Step 1: set beg = lower_bound, end = upper_bound, pos = - 1 Step 2: repeat steps 3 and 4 while beg val set end = mid - 1 else set beg = mid + 1 [end of if] [end of loop] Step 5: if pos = -1 print 'value is not present in the array' [end of if] Step 6: exit
İkili aramanın çalışması
Şimdi İkili Arama Algoritmasının çalışmasına bakalım.
İkili arama algoritmasının çalışmasını anlamak için sıralanmış bir diziyi ele alalım. İkili aramanın işleyişini bir örnekle anlamak kolay olacaktır.
İkili arama algoritmasını uygulamanın iki yöntemi vardır:
- Yinelemeli yöntem
- Özyinelemeli yöntem
Özyinelemeli ikili arama yöntemi, böl ve yönet yaklaşımını takip eder.
Dizinin elemanları şöyle olsun:
Aranacak öğenin şu olmasına izin verin: K = 56
Hesaplamak için aşağıdaki formülü kullanmamız gerekiyor. orta dizinin -
mid = (beg + end)/2
Yani verilen dizide -
dilenmek = 0
son = 8
Shilpa Shetty'nin yaşı
orta = (0 + 8)/2 = 4. Yani 4 dizinin ortasıdır.
Artık aranacak öğe bulundu. Böylece algoritma eşleşen öğenin indeksini döndürecektir.
İkili Arama karmaşıklığı
Şimdi en iyi durumda, ortalama durumda ve en kötü durumda İkili aramanın zaman karmaşıklığını görelim. Ayrıca İkili aramanın uzay karmaşıklığını da göreceğiz.
1. Zaman Karmaşıklığı
| Dava | Zaman Karmaşıklığı |
|---|---|
| En iyi senaryo | Ç(1) |
| Ortalama Durum | O(giriş) |
| En kötü durumda | O(giriş) |
2. Uzayın Karmaşıklığı
| Uzay Karmaşıklığı | Ç(1) |
- İkili aramanın uzay karmaşıklığı O(1)'dir.
İkili Aramanın Uygulanması
Şimdi farklı programlama dillerindeki İkili arama programlarını görelim.
Program: C dilinde İkili aramayı uygulayan bir program yazın.
#include int binarySearch(int a[], int beg, int end, int val) { int mid; if(end >= beg) { mid = (beg + end)/2; /* if the item to be searched is present at middle */ if(a[mid] == val) { return mid+1; } /* if the item to be searched is smaller than middle, then it can only be in left subarray */ else if(a[mid] <val) { return binarysearch(a, mid+1, end, val); } * if the item to be searched is greater than middle, then it can only in right subarray else beg, mid-1, -1; int main() a[]="{11," 14, 25, 30, 40, 41, 52, 57, 70}; given array val="40;" value n="sizeof(a)" sizeof(a[0]); size of res="binarySearch(a," 0, n-1, store result printf('the elements are - '); for (int i="0;" < n; i++) printf('%d ', a[i]); printf('
element %d', (res="=" -1) not present array'); at %d position array', res); 0; pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/10/binary-search-algorithm-5.webp" alt="Binary Search Algorithm"> <p> <strong>Program:</strong> Write a program to implement Binary search in C++.</p> <pre> #include using namespace std; int binarySearch(int a[], int beg, int end, int val) { int mid; if(end >= beg) { mid = (beg + end)/2; /* if the item to be searched is present at middle */ if(a[mid] == val) { return mid+1; } /* if the item to be searched is smaller than middle, then it can only be in left subarray */ else if(a[mid] <val) { return binarysearch(a, mid+1, end, val); } * if the item to be searched is greater than middle, then it can only in right subarray else beg, mid-1, -1; int main() a[]="{10," 12, 24, 29, 39, 40, 51, 56, 70}; given array val="51;" value n="sizeof(a)" sizeof(a[0]); size of res="binarySearch(a," 0, n-1, store result cout<<'the elements are - '; for (int i="0;" < n; i++) cout< <a[i]<<' cout<<'
element '<<val; (res="=" -1) not present array'; at '<<res<<' position 0; pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/10/binary-search-algorithm-6.webp" alt="Binary Search Algorithm"> <p> <strong>Program:</strong> Write a program to implement Binary search in C#.</p> <pre> using System; class BinarySearch { static int binarySearch(int[] a, int beg, int end, int val) { int mid; if(end >= beg) { mid = (beg + end)/2; if(a[mid] == val) { return mid+1; /* if the item to be searched is present at middle */ } /* if the item to be searched is smaller than middle, then it can only be in left subarray */ else if(a[mid] <val) { return binarysearch(a, mid+1, end, val); } * if the item to be searched is greater than middle, then it can only in right subarray else beg, mid-1, -1; static void main() int[] a="{9," 11, 23, 28, 38, 45, 50, 56, 70}; given array int val="70;" value n="a.Length;" size of res="binarySearch(a," 0, n-1, store result console.write('the elements are - '); for (int i="0;" < n; i++) console.write(a[i] + ' console.writeline(); console.writeline('element (res="=" -1) not present array'); at position pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/10/binary-search-algorithm-7.webp" alt="Binary Search Algorithm"> <p> <strong>Program:</strong> Write a program to implement Binary search in Java.</p> <pre> class BinarySearch { static int binarySearch(int a[], int beg, int end, int val) { int mid; if(end >= beg) { mid = (beg + end)/2; if(a[mid] == val) { return mid+1; /* if the item to be searched is present at middle */ } /* if the item to be searched is smaller than middle, then it can only be in left subarray */ else if(a[mid] <val) { return binarysearch(a, mid+1, end, val); } * if the item to be searched is greater than middle, then it can only in right subarray else beg, mid-1, -1; public static void main(string args[]) int a[]="{8," 10, 22, 27, 37, 44, 49, 55, 69}; given array val="37;" value n="a.length;" size of res="binarySearch(a," 0, n-1, store result system.out.print('the elements are: '); for (int i="0;" < n; i++) system.out.print(a[i] + ' system.out.println(); system.out.println('element is: (res="=" -1) not present array'); at position pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/10/binary-search-algorithm-8.webp" alt="Binary Search Algorithm"> <p> <strong>Program:</strong> Write a program to implement Binary search in PHP.</p> <pre> = $beg) { $mid = floor(($beg + $end)/2); if($a[$mid] == $val) { return $mid+1; /* if the item to be searched is present at middle */ } /* if the item to be searched is smaller than middle, then it can only be in left subarray */ else if($a[$mid] <$val) { return binarysearch($a, $mid+1, $end, $val); } * if the item to be searched is greater than middle, then it can only in right subarray else $beg, $mid-1, -1; $a="array(7," 9, 21, 26, 36, 43, 48, 54, 68); given array $val="68;" value $n="sizeof($a);" size of $res="binarySearch($a," 0, $n-1, store result echo 'the elements are: '; for ($i="0;" $i < $n; $i++) ' , $a[$i]; <br>' , 'Element to be searched is: ' , $val; if ($res == -1) echo ' <br>' , 'Element is not present in the array'; else echo ' <br>' , 'Element is present at ' , $res , ' position of array'; ?> </$val)></pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/10/binary-search-algorithm-9.webp" alt="Binary Search Algorithm"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <hr></val)></pre></val)></pre></val)></pre></val)> Çıktı
Yani bu makaleyle ilgili. Umarım makale sizin için yararlı ve bilgilendirici olacaktır.