{"id":561,"date":"2014-12-31T11:54:58","date_gmt":"2014-12-31T10:54:58","guid":{"rendered":"http:\/\/www.valcon.it\/pascal\/?p=561"},"modified":"2015-07-03T11:34:51","modified_gmt":"2015-07-03T09:34:51","slug":"ricerca-binaria","status":"publish","type":"post","link":"https:\/\/www.valcon.it\/pascal\/ricerca-binaria\/","title":{"rendered":"Ricerca binaria"},"content":{"rendered":"<p>La ricerca binaria si applica agli array ordinati.<\/p>\n<p>Essa controlla se l&#8217;elemento richiesto si trova nella posizione centrale dell&#8217;array altrimenti concentra la ricerca nella parte<\/p>\n<ul>\n<li>BASSA se ha trovato un elemento MAGGIORE<\/li>\n<li>ALTA se ha trovato un elemento MINORE<\/li>\n<\/ul>\n<p>e continua finch\u00e9<\/p>\n<ul>\n<li>non trova l&#8217;elemento,<\/li>\n<li>oppure rimane da esaminare un sottoarray vuoto.<\/li>\n<\/ul>\n<h4>Esempio<\/h4>\n<p>Sia V = (<strong>10<\/strong>, <strong>25<\/strong>, <strong>30<\/strong>, <strong>40<\/strong>, <strong>41<\/strong>, <strong>42<\/strong>, <strong>60<\/strong>)<\/p>\n<table>\n<tbody>\n<tr valign=\"top\">\n<td>Nel caso ottimo, l&#8217;elemento richiesto occupa la posizione centrale e basta un unico passo<\/td>\n<td><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-566 size-full\" src=\"http:\/\/www.valcon.it\/pascal\/wp-content\/uploads\/rb1.png\" alt=\"rb1\" width=\"505\" height=\"120\" srcset=\"https:\/\/www.valcon.it\/pascal\/wp-content\/uploads\/rb1.png 505w, https:\/\/www.valcon.it\/pascal\/wp-content\/uploads\/rb1-150x36.png 150w, https:\/\/www.valcon.it\/pascal\/wp-content\/uploads\/rb1-300x71.png 300w\" sizes=\"(max-width: 505px) 100vw, 505px\" \/><\/td>\n<\/tr>\n<tr valign=\"top\">\n<td>Nel caso pessimo, sono necessari 3 passi<\/td>\n<td><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-567 size-full\" src=\"http:\/\/www.valcon.it\/pascal\/wp-content\/uploads\/rb2.png\" alt=\"rb2\" width=\"505\" height=\"220\" srcset=\"https:\/\/www.valcon.it\/pascal\/wp-content\/uploads\/rb2.png 505w, https:\/\/www.valcon.it\/pascal\/wp-content\/uploads\/rb2-150x65.png 150w, https:\/\/www.valcon.it\/pascal\/wp-content\/uploads\/rb2-300x131.png 300w\" sizes=\"(max-width: 505px) 100vw, 505px\" \/><\/td>\n<\/tr>\n<tr valign=\"top\">\n<td>Se l&#8217;elemento non \u00e8 presente si scopre dopo i 3 passi del caso pessimo.<\/td>\n<td><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-947\" src=\"http:\/\/www.valcon.it\/pascal\/wp-content\/uploads\/rb3p.png\" alt=\"rb3p\" width=\"506\" height=\"270\" srcset=\"https:\/\/www.valcon.it\/pascal\/wp-content\/uploads\/rb3p.png 506w, https:\/\/www.valcon.it\/pascal\/wp-content\/uploads\/rb3p-150x80.png 150w, https:\/\/www.valcon.it\/pascal\/wp-content\/uploads\/rb3p-300x160.png 300w\" sizes=\"(max-width: 506px) 100vw, 506px\" \/><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<pre class=\"\">Function Binaria(V: Vettore; N: Integer; K: Real): Integer;\r\nVar\r\n \u00a0 INF   ,\r\n   SUP   ,\r\n   MEDIO : Integer;\r\n \u00a0 ANCORA: Boolean;\r\nBegin\r\n \u00a0 INF:=1;\r\n \u00a0 SUP:=N;\r\n \u00a0 ANCORA:=True;\r\n \u00a0 While(INF &lt;= SUP) And (ANCORA) Do\r\n \u00a0 \u00a0  Begin\r\n \u00a0 \u00a0 \u00a0 \u00a0 MEDIO:=(INF+SUP) Div 2;\r\n \u00a0 \u00a0 \u00a0 \u00a0 If(V[MEDIO] &lt; K) Then\r\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 INF:=MEDIO+1\r\n \u00a0 \u00a0 \u00a0 \u00a0 Else If(V[MEDIO] = K) Then\r\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 ANCORA:=False\r\n \u00a0 \u00a0 \u00a0 \u00a0 Else\r\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 SUP:=MEDIO-1;\r\n\u00a0 \u00a0 \u00a0 End;\r\n\u00a0  If(ANCORA) Then\r\n\u00a0 \u00a0 \u00a0 Binaria:=0\r\n \u00a0 Else\r\n\u00a0 \u00a0 \u00a0 Binaria:=MEDIO;\r\nEnd;<\/pre>\n<p>Semplifico<\/p>\n<pre class=\"\">Function Binaria(V: Vettore; N: Integer; K: Real): Integer;\r\nVar\r\n \u00a0 INF  ,\r\n   SUP  ,\r\n   MEDIO: Integer;\r\n \u00a0 RISP : Integer; \r\nBegin\r\n \u00a0 INF:=1;\r\n \u00a0 SUP:=N;\r\n \u00a0 RISP:=0;\r\n \u00a0 While(INF &lt;= SUP) And (RISP = 0) Do\r\n\u00a0 \u00a0 \u00a0 Begin\r\n \u00a0 \u00a0 \u00a0 \u00a0 MEDIO:=(INF+SUP) Div 2;\r\n \u00a0 \u00a0 \u00a0 \u00a0 If(V[MEDIO] &lt; K) Then\r\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 INF:=MEDIO+1\r\n \u00a0 \u00a0 \u00a0 \u00a0 Else if(V[MEDIO] = K) Then\r\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 RISP:=MEDIO\r\n \u00a0 \u00a0 \u00a0 \u00a0 Else\r\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 SUP:=MEDIO-1;\r\n \u00a0 \u00a0  End;\r\n\u00a0  Binaria:=RISP; \r\nEnd;<\/pre>\n<hr\/>\n<p>Analizziamo il codice<\/p>\n<pre>Function ricercaBinaria(V: Vettore; N: Integer; K: Real): Integer;\r\nVar\r\n \u00a0 INF  ,\r\n   SUP  ,\r\n   MEDIO,\r\n \u00a0 RISP : Integer;\r\nBegin\r\n \u00a0 INF :=1;\r\n \u00a0 SUP :=N;\r\n \u00a0 RISP:=0;\r\n \u00a0 While(INF <= SUP) And (RISP = 0) do\r\n \u00a0 \u00a0 \u00a0Begin\r\n\u00a0 \u00a0 \u00a0  \u00a0 MEDIO:=(INF+SUP) Div 2;\r\n\u00a0 \u00a0 \u00a0  \u00a0 If(V[MEDIO] < K) Then\r\n \u00a0 \u00a0 \u00a0\u00a0 \u00a0 \u00a0 INF:=MEDIO+1\r\n\u00a0 \u00a0 \u00a0  \u00a0 Else if(V[MEDIO] = K) Then\r\n \u00a0 \u00a0 \u00a0\u00a0 \u00a0 \u00a0 RISP:=MEDIO\r\n\u00a0 \u00a0 \u00a0  \u00a0 Else\r\n \u00a0 \u00a0 \u00a0\u00a0 \u00a0 \u00a0 SUP:=MEDIO-1;\r\n\u00a0 \u00a0 \u00a0 End;\r\n\u00a0 \u00a0ricercaBinaria:=RISP;\r\nEnd;<\/pre>\n<p>Utilizzando la <a title=\"Complessit\u00e0: ricerca sequenziale\" href=\"http:\/\/www.valcon.it\/pascal\/complessita-ricerca-sequenziale\/\">tecnica di calcolo<\/a> della complessit\u00e0 in tempo possiamo concludere che<\/p>\n<div class=\"indent\" style=\"padding-left: 30px;\">T(x) = c<sub>1<\/sub>+c<sub>2<\/sub>x<\/div>\n<p>con x il numero di volte che viene eseguito il ciclo.<\/p>\n<p>I calcoli approssimati per T danno<\/p>\n<ul>\n<li>vettore vuoto: <tt>~7<\/tt><\/li>\n<li>elemento trovato al 1\u00b0 passo (in mezzo): <tt>c<sub>1<\/sub>+c<sub>2<\/sub>*1<\/tt><\/li>\n<li>elemento trovato al 2\u00b0 passo: <tt>c<sub>1<\/sub>+c<sub>2<\/sub>*2<\/tt><\/li>\n<li>...<\/li>\n<li>elemento trovato all'ultimo passo: <tt>c<sub>1<\/sub>+c<sub>2<\/sub>*(m-1)<\/tt><\/li>\n<li>elemento non presente: <tt>c<sub>1<\/sub>+c<sub>2<\/sub>*m<\/tt><\/li>\n<\/ul>\n<p>Supponiamo pessimisticamente di dover aspettare sempre fino all'ultimo passo, allora<\/p>\n<div class=\"indent\" style=\"padding-left: 30px;\"><tt>T(n)=c<sub>1<\/sub>+c<sub>2<\/sub>*m<\/tt>.<\/div>\n<h3>Quanto vale m?<\/h3>\n<p>La dimensione del vettore sul quale si effettua la ricerca passo-passo \u00e8<\/p>\n<ul>\n<li><tt>n<\/tt><\/li>\n<li><tt>~n\/2<\/tt><\/li>\n<li><tt>~n\/4<\/tt><\/li>\n<li><tt>~n\/8<\/tt><\/li>\n<li><tt>...<\/tt><\/li>\n<li><tt>2<\/tt><\/li>\n<li><tt>1<\/tt><\/li>\n<li><tt>0<\/tt> ...<\/li>\n<\/ul>\n<p>Quando il valore della potenza di <strong>2<\/strong> a denominatore raggiunge <strong>n<\/strong> il ciclo termina sicuramente, cio\u00e8 per<\/p>\n<div class=\"indent\" style=\"padding-left: 30px;\"><tt>2<sup>m<\/sup> = n<br \/>\nm = log<sub>2<\/sub>n<\/tt><\/div>\n<p>quindi, nel caso pessimo<\/p>\n<div class=\"indent\" style=\"padding-left: 30px;\"><tt>T(n) = c<sub>1<\/sub>+c<sub>2<\/sub>m = c<sub>1<\/sub>+c<sub>2<\/sub>log<sub>2<\/sub>n<\/tt><\/div>\n<h3>Esempi numerici<\/h3>\n<table class=\"data\">\n<tbody>\n<tr align=\"center\">\n<td colspan=\"2\">n<\/td>\n<td>m<\/td>\n<\/tr>\n<tr align=\"right\">\n<td style=\"text-align: center;\">2<sup>4<\/sup><\/td>\n<td>16<\/td>\n<td>4<\/td>\n<\/tr>\n<tr align=\"right\">\n<td style=\"text-align: center;\">2<sup>8<\/sup><\/td>\n<td>256<\/td>\n<td>8<\/td>\n<\/tr>\n<tr align=\"right\">\n<td style=\"text-align: center;\">2<sup>10<\/sup><\/td>\n<td>1.024<\/td>\n<td>10<\/td>\n<\/tr>\n<tr align=\"right\">\n<td style=\"text-align: center;\">2<sup>16<\/sup><\/td>\n<td>65.536<\/td>\n<td>16<\/td>\n<\/tr>\n<tr align=\"right\">\n<td style=\"text-align: center;\">2<sup>20<\/sup><\/td>\n<td>1.048.576<\/td>\n<td>20<\/td>\n<\/tr>\n<tr align=\"right\">\n<td style=\"text-align: center;\">2<sup>30<\/sup><\/td>\n<td>1.073.741.824<\/td>\n<td>30<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>L'algoritmo di ricerca binaria applicato a un vettore con <strong>un miliardo<\/strong> di elementi garantisce una risposta dopo appena <strong>30 passi<\/strong>!<\/p>\n","protected":false},"excerpt":{"rendered":"<p>La ricerca binaria si applica agli array ordinati. Essa controlla se l&#8217;elemento richiesto si trova nella posizione centrale dell&#8217;array altrimenti concentra la ricerca nella parte BASSA se ha trovato un elemento MAGGIORE ALTA se ha trovato un elemento MINORE e continua finch\u00e9 non trova l&#8217;elemento, oppure rimane da esaminare un sottoarray vuoto. Esempio Sia V &#8230; <a title=\"Ricerca binaria\" class=\"read-more\" href=\"https:\/\/www.valcon.it\/pascal\/ricerca-binaria\/\" aria-label=\"Leggi di pi\u00f9 su Ricerca binaria\">Leggi tutto<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[10],"tags":[],"_links":{"self":[{"href":"https:\/\/www.valcon.it\/pascal\/wp-json\/wp\/v2\/posts\/561"}],"collection":[{"href":"https:\/\/www.valcon.it\/pascal\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.valcon.it\/pascal\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.valcon.it\/pascal\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.valcon.it\/pascal\/wp-json\/wp\/v2\/comments?post=561"}],"version-history":[{"count":10,"href":"https:\/\/www.valcon.it\/pascal\/wp-json\/wp\/v2\/posts\/561\/revisions"}],"predecessor-version":[{"id":5645,"href":"https:\/\/www.valcon.it\/pascal\/wp-json\/wp\/v2\/posts\/561\/revisions\/5645"}],"wp:attachment":[{"href":"https:\/\/www.valcon.it\/pascal\/wp-json\/wp\/v2\/media?parent=561"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.valcon.it\/pascal\/wp-json\/wp\/v2\/categories?post=561"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.valcon.it\/pascal\/wp-json\/wp\/v2\/tags?post=561"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}