Tässä artikkelissa käsittelemme binäärihakualgoritmia. Haku on prosessi, jolla löydetään jokin tietty elementti luettelosta. Jos elementti on luettelossa, prosessia kutsutaan onnistuneeksi ja prosessi palauttaa kyseisen elementin sijainnin. Muussa tapauksessa hakua kutsutaan epäonnistuneeksi.
Lineaarinen haku ja binäärihaku ovat kaksi suosittua hakutekniikkaa. Täällä keskustelemme binäärihakualgoritmista.
Binäärihaku on hakutekniikka, joka toimii tehokkaasti lajiteltujen listojen kanssa. Siksi, jotta voimme etsiä elementin jostain luettelosta binäärihakutekniikalla, meidän on varmistettava, että luettelo on lajiteltu.
Binäärihaku noudattaa hajota ja hallitse -lähestymistapaa, jossa lista jaetaan kahteen osaan ja kohdetta verrataan listan keskielementtiin. Jos vastaavuus löytyy silloin, keskimmäisen elementin sijainti palautetaan. Muussa tapauksessa etsimme jompaakumpaa puoliaikaa ottelun aikana saadun tuloksen mukaan.
HUOMAA: Binaarihaku voidaan toteuttaa lajiteltuihin taulukkoelementteihin. Jos luettelon elementtejä ei ole järjestetty järjestykseen, meidän on ensin lajiteltava ne.
Katsotaanpa nyt binaarihaun algoritmia.
Algoritmi
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
Binaarihaun toiminta
Katsotaanpa nyt binaarihakualgoritmin toimintaa.
Ymmärtääksemme binaarihakualgoritmin toiminnan, otetaan lajiteltu matriisi. Binaarihaun toiminta on helppo ymmärtää esimerkin avulla.
Binäärihakualgoritmin toteuttamiseen on kaksi tapaa -
- Iteratiivinen menetelmä
- Rekursiivinen menetelmä
Binäärihaun rekursiivinen menetelmä noudattaa hajota ja hallitse -lähestymistapaa.
Olkoon taulukon elementit -
Olkoon etsittävä elementti, K = 56
Meidän on käytettävä alla olevaa kaavaa laskeaksemme mid joukosta -
mid = (beg + end)/2
Joten annetussa taulukossa -
kerjätä = 0
loppu = 8
mid = (0 + 8)/2 = 4. Joten 4 on taulukon keskikohta.
Nyt etsittävä elementti löytyy. Joten algoritmi palauttaa osuvan elementin indeksin.
Binaarihaun monimutkaisuus
Katsotaan nyt binaarihaun aikamonimutkaisuus parhaassa tapauksessa, keskimääräisessä tapauksessa ja pahimmassa tapauksessa. Näemme myös binaarihaun avaruuden monimutkaisuuden.
1. Aika monimutkaisuus
| Asia | Aika monimutkaisuus |
|---|---|
| Paras tapaus | O(1) |
| Keskimääräinen tapaus | O (kirjaudu sisään) |
| Pahimmassa tapauksessa | O (kirjaudu sisään) |
2. Tilan monimutkaisuus
| Avaruuden monimutkaisuus | O(1) |
- Binäärihaun avaruuskompleksisuus on O(1).
Binaarihaun käyttöönotto
Katsotaanpa nyt binaarihaun ohjelmia eri ohjelmointikielillä.
Ohjelmoida: Kirjoita ohjelma binaarihaun toteuttamiseksi C-kielellä.
#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)> Lähtö
Eli siinä kaikki artikkelista. Toivottavasti artikkeli on hyödyllinen ja informatiivinen sinulle.