Ebben a cikkben a bináris keresési algoritmusról fogunk beszélni. A keresés egy bizonyos elem megtalálásának folyamata a listában. Ha az elem szerepel a listában, akkor a folyamatot sikeresnek nevezzük, és a folyamat visszaadja az elem helyét. Ellenkező esetben a keresést sikertelennek nevezzük.
A lineáris keresés és a bináris keresés a két népszerű keresési technika. Itt a bináris keresési algoritmusról fogunk beszélni.
A bináris keresés az a keresési technika, amely hatékonyan működik rendezett listákon. Ezért, ha egy elemet valamilyen listában akarunk keresni a bináris keresési technikával, gondoskodnunk kell a lista rendezettségéről.
A bináris keresés az oszd meg és uralkodj megközelítést követi, amelyben a listát két részre osztják, és az elemet összehasonlítják a lista középső elemével. Ha megtaláltuk az egyezést, akkor a középső elem helye kerül visszaadásra. Ellenkező esetben a meccsen elért eredménytől függően bármelyik félidőben keresünk.
MEGJEGYZÉS: A bináris keresés megvalósítható rendezett tömbelemeken. Ha a listaelemek nincsenek rendezetten elrendezve, először rendeznünk kell őket.
Most pedig lássuk a bináris keresés algoritmusát.
Algoritmus
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
A bináris keresés működése
Most pedig lássuk a bináris keresési algoritmus működését.
jdbc
A bináris keresési algoritmus működésének megértéséhez vegyünk egy rendezett tömböt. Könnyű lesz megérteni a bináris keresés működését egy példán keresztül.
Két módszer létezik a bináris keresési algoritmus megvalósítására:
- Iteratív módszer
- Rekurzív módszer
A bináris keresés rekurzív módszere az oszd meg és uralkodj megközelítést követi.
Legyen a tömb elemei -
Legyen a keresendő elem, K = 56
Kiszámításához az alábbi képletet kell használnunk középső a tömbből -
mid = (beg + end)/2
Tehát az adott tömbben -
könyörög = 0
nfa a dfa
vége = 8
középső = (0 + 8)/2 = 4. Tehát a 4 a tömb közepe.
java swing oktatóanyag
Most megtaláltuk a keresendő elemet. Tehát az algoritmus az illesztett elem indexét adja vissza.
Bináris keresés összetettsége
Most pedig lássuk a bináris keresés időbeli összetettségét a legjobb, az átlagos és a legrosszabb esetben. Látni fogjuk a Bináris keresés térbeli összetettségét is.
1. Időbonyolultság
| Ügy | Idő összetettsége |
|---|---|
| Legjobb eset | O(1) |
| Átlagos eset | O(bejelentkezés) |
| Legrosszabb esetben | O(bejelentkezés) |
2. A tér összetettsége
| A tér összetettsége | O(1) |
- A bináris keresés térkomplexitása O(1).
A bináris keresés megvalósítása
Most pedig lássuk a Bináris keresés programjait különböző programozási nyelveken.
Program: Írjon programot a bináris keresés megvalósítására C nyelven.
#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)> Kimenet
Szóval ennyi a cikkről. Reméljük, hogy a cikk hasznos és informatív lesz az Ön számára.