Program For Binary Search[How to]

<div dir="ltr" style="text-align: left;" trbidi="on"> <span style="font-family: Trebuchet MS, sans-serif;"><br /> </span><br /> <h2 style="text-align: left;"> <div class="MsoNormal" style="text-align: left;"> <b><span style="font-family: Trebuchet MS, sans-serif;"><span style="background-color: white; background-position: initial initial; background-repeat: initial initial; font-size: 18pt;">                                </span><span style="background-color: white;"><span style="font-size: 18pt;">   </span><span style="font-size: 18pt;"> </span></span><span style="font-size: 18pt;"><span style="background-color: white;">Binary Search</span><span style="background-color: white;"><o:p></o:p></span></span></span></b></div> </h2> <h2 style="text-align: left;"> <span style="font-family: Trebuchet MS, sans-serif;"><span style="background: white;">   Goal--</span><span style="background: white;">How to do Binary Search In a Given Array?</span></span></h2> <h2 style="text-align: left;"> <span style="background-color: white; font-family: Trebuchet MS, sans-serif;">   Method Used-- Divide and Conquer</span></h2> <h2 style="text-align: center;"> <span style="font-family: Trebuchet MS, sans-serif;"><o:p></o:p></span></h2> <h2> <div class="MsoNormal" style="text-align: left;"> <h2 style="text-align: left;"> <span style="font-family: Trebuchet MS, sans-serif; font-size: large;"><span style="background-color: white;">    Explanation</span><span style="background-color: white;">:</span></span></h2> <h2 style="text-align: left;"> <span style="font-family: Trebuchet MS, sans-serif;"><span style="background-color: white; font-size: 13.5pt;">                              Binary Search is best Example of Divide and Conquer Technique.</span><span style="background-color: white; font-size: 13.5pt;">In this first we divide the Problem into Sub problem such that  solution to that sub problem is solution for our real problem.</span></span></h2> <h2 style="text-align: left;"> <span style="font-family: Trebuchet MS, sans-serif;"><span style="background-color: white; font-size: 13.5pt;">As we all know that </span><span style="color: red; font-size: 13.5pt;">**Binary search is always performed on sorted array.**</span></span></h2> <h2 style="text-align: left;"> <b><span style="background-color: white; background-position: initial initial; background-repeat: initial initial; font-family: Trebuchet MS, sans-serif; font-size: 13.5pt;">Steps:</span></b></h2> <h2 style="text-align: left;"> <span style="background-color: white; font-family: Trebuchet MS, sans-serif; font-size: 13.5pt;">1.Calculate middle element of Given Array. </span></h2> <h2 style="text-align: left;"> <span style="background-color: white; font-family: Trebuchet MS, sans-serif; font-size: 13.5pt;"> 2. Compare middle element with given number. Then there will be three Cases:                           </span></h2> <h2 style="text-align: left;"> <span style="background-color: white; font-family: Trebuchet MS, sans-serif; font-size: 13.5pt;">           2.1 Given number is equal to middle element  then return it as</span></h2> <h2 style="text-align: left;"> <span style="background-color: white; font-family: Trebuchet MS, sans-serif; font-size: 13.5pt;">           result.</span></h2> <h2 style="text-align: left;"> <span style="background-color: white; font-family: Trebuchet MS, sans-serif; font-size: 13.5pt;">           2.2 If Given number is less than middle  element,then replace</span></h2> <h2 style="text-align: left;"> <span style="background-color: white; font-family: Trebuchet MS, sans-serif; font-size: 13.5pt;">          given array with left half of the given array. Go to step1.</span></h2> <h2 style="text-align: left;"> <span style="background-color: white; font-family: Trebuchet MS, sans-serif; font-size: 13.5pt;">           2.3 If Middle element is greater than given element then replace</span></h2> <h2 style="text-align: left;"> <span style="font-family: Trebuchet MS, sans-serif;"><span style="background-color: white; font-size: 13.5pt;">           the </span><span style="background-color: white; font-size: 13.5pt;">given array with right half of the given array.  Go to step 1.</span></span></h2> <h2 style="text-align: left;"> <span style="font-family: Trebuchet MS, sans-serif;"><span style="background-color: white; font-size: 13.5pt;">3. Perform Above steps Until you finds the given element otherwise </span><span style="background-color: white; font-size: 13.5pt;">return False.</span></span></h2> <h2 style="text-align: left;"> <span style="font-family: Trebuchet MS, sans-serif; font-size: large;"><span style="background-color: white;"><o:p></o:p></span><b><span style="background-color: white; line-height: 115%;">Program:</span></b></span></h2> <h2 style="text-align: left;"> <span style="font-family: Trebuchet MS, sans-serif;"><span style="background-color: white; font-size: 13.5pt; line-height: 115%;">This Program is in c++, but if you are clear with concept you can </span><span style="background-color: white; font-size: 13.5pt; line-height: 115%;">implement in any language.</span></span></h2> </div> <div style="font-weight: bold; text-align: left;"> <i style="background-color: white; font-size: large; line-height: 20px;"><span style="font-family: Trebuchet MS, sans-serif;">#include <iostream></span></i></div> <div style="text-align: left;"> <span style="font-family: Trebuchet MS, sans-serif;"><i style="background-color: white;"> </i> </span><br /> <div> <span style="font-size: medium;"><span style="font-family: Trebuchet MS, sans-serif; line-height: 20px;"><i style="background-color: white;">#include<conio.h></i></span></span></div> <div> <span style="font-size: medium;"><span style="font-family: Trebuchet MS, sans-serif; line-height: 20px;"><i style="background-color: white;">using namespace std;</i></span></span></div> <div> <span style="font-size: medium;"><span style="font-family: Trebuchet MS, sans-serif; line-height: 20px;"><i style="background-color: white;">int main()</i></span></span></div> <div> <span style="font-size: medium;"><span style="font-family: Trebuchet MS, sans-serif; line-height: 20px;"><i style="background-color: white;">       {</i></span></span></div> <div> <span style="font-size: medium;"><span style="font-family: Trebuchet MS, sans-serif; line-height: 20px;"><i style="background-color: white;">            int a[30],num,p[30];</i></span></span></div> <div> <span style="font-size: medium;"><span style="font-family: Trebuchet MS, sans-serif; line-height: 20px;"><i style="background-color: white;">            int end,mid,i,k,beg;</i></span></span></div> <div> <span style="font-size: medium;"><span style="font-family: Trebuchet MS, sans-serif; line-height: 20px;"><i style="background-color: white;">            beg=0;</i></span></span></div> <div> <span style="font-size: medium;"><span style="font-family: Trebuchet MS, sans-serif; line-height: 20px;"><i style="background-color: white;">            cout<<"How many elements you want to have in array\n";</i></span></span></div> <div> <span style="font-size: medium;"><span style="font-family: Trebuchet MS, sans-serif; line-height: 20px;"><i style="background-color: white;">            cin>>k;</i></span></span></div> <div> <span style="font-size: medium;"><span style="font-family: Trebuchet MS, sans-serif; line-height: 20px;"><i style="background-color: white;">            cout<<"Enter Elements of Array:\n";</i></span></span></div> <div> <span style="font-size: medium;"><span style="font-family: Trebuchet MS, sans-serif; line-height: 20px;"><i style="background-color: white;">            for(i=0;i<k;i++)</i></span></span></div> <div> <span style="font-size: medium;"><span style="font-family: Trebuchet MS, sans-serif; line-height: 20px;"><i style="background-color: white;">             {</i></span></span></div> <div> <span style="font-size: medium;"><span style="font-family: Trebuchet MS, sans-serif; line-height: 20px;"><i style="background-color: white;">                             cin>>a[i];</i></span></span></div> <div> <span style="font-size: medium;"><span style="font-family: Trebuchet MS, sans-serif; line-height: 20px;"><i style="background-color: white;">                             p[i]=i;</i></span></span></div> <div> <span style="font-size: medium;"><span style="font-family: Trebuchet MS, sans-serif; line-height: 20px;"><i style="background-color: white;">             }</i></span></span></div> <div> <span style="font-size: medium;"><span style="font-family: Trebuchet MS, sans-serif; line-height: 20px;"><i style="background-color: white;">            cout<<"Enter element to be search\n"; </i></span></span></div> <div> <span style="font-size: medium;"><span style="font-family: Trebuchet MS, sans-serif; line-height: 20px;"><i style="background-color: white;">            cin>>num;</i></span></span></div> <div> <span style="font-size: medium;"><span style="font-family: Trebuchet MS, sans-serif; line-height: 20px;"><i style="background-color: white;">            /*First we sort the enter bcoz Binary search is always performed on sorted list..*/</i></span></span></div> <div> <span style="font-size: medium;"><span style="font-family: Trebuchet MS, sans-serif; line-height: 20px;"><i style="background-color: white;">           for(i=0;i<k;i++)</i></span></span></div> <div> <span style="font-size: medium;"><span style="font-family: Trebuchet MS, sans-serif; line-height: 20px;"><i style="background-color: white;">              {</i></span></span></div> <div> <span style="font-size: medium;"><span style="font-family: Trebuchet MS, sans-serif; line-height: 20px;"><i style="background-color: white;">                int j;</i></span></span></div> <div> <span style="font-size: medium;"><span style="font-family: Trebuchet MS, sans-serif; line-height: 20px;"><i style="background-color: white;">                for(j=0;j<k;j++)</i></span></span></div> <div> <span style="font-size: medium;"><span style="font-family: Trebuchet MS, sans-serif; line-height: 20px;"><i style="background-color: white;">                   {</i></span></span></div> <div> <span style="font-size: medium;"><span style="font-family: Trebuchet MS, sans-serif; line-height: 20px;"><i style="background-color: white;">                      if(a[i]<a[j])</i></span></span></div> <div> <span style="font-size: medium;"><span style="font-family: Trebuchet MS, sans-serif; line-height: 20px;"><i style="background-color: white;">                        {</i></span></span></div> <div> <span style="font-size: medium;"><span style="font-family: Trebuchet MS, sans-serif; line-height: 20px;"><i style="background-color: white;">                           int temp=a[i];</i></span></span></div> <div> <span style="font-size: medium;"><span style="font-family: Trebuchet MS, sans-serif; line-height: 20px;"><i style="background-color: white;">                            a[i]=a[j];</i></span></span></div> <div> <span style="font-size: medium;"><span style="font-family: Trebuchet MS, sans-serif; line-height: 20px;"><i style="background-color: white;">                            a[j]=temp;</i></span></span></div> <div> <span style="font-size: medium;"><span style="font-family: Trebuchet MS, sans-serif; line-height: 20px;"><i style="background-color: white;">                            temp=p[i];</i></span></span></div> <div> <span style="font-size: medium;"><span style="font-family: Trebuchet MS, sans-serif; line-height: 20px;"><i style="background-color: white;">                            p[i]=p[j];</i></span></span></div> <div> <span style="font-size: medium;"><span style="font-family: Trebuchet MS, sans-serif; line-height: 20px;"><i style="background-color: white;">                            p[j]=temp;</i></span></span></div> <div> <span style="font-size: medium;"><span style="font-family: Trebuchet MS, sans-serif; line-height: 20px;"><i style="background-color: white;">                        }   </i></span></span></div> <div> <span style="font-size: medium;"><span style="font-family: Trebuchet MS, sans-serif; line-height: 20px;"><i style="background-color: white;">                   }  </i></span></span></div> <div> <span style="font-size: medium;"><span style="font-family: Trebuchet MS, sans-serif; line-height: 20px;"><i style="background-color: white;">                }    </i></span></span></div> <div> <span style="font-size: medium;"><span style="font-family: Trebuchet MS, sans-serif; line-height: 20px;"><i style="background-color: white;">             end=k-1;</i></span></span></div> <div> <span style="font-size: medium;"><span style="font-family: Trebuchet MS, sans-serif; line-height: 20px;"><i style="background-color: white;">            mid=int((end+beg)/2); //because our index start from 0(beg).</i></span></span></div> <div> <span style="font-size: medium;"><span style="font-family: Trebuchet MS, sans-serif; line-height: 20px;"><i style="background-color: white;">            while(beg<=end & a[mid]!=num)           </i></span></span></div> <div> <span style="font-size: medium;"><span style="font-family: Trebuchet MS, sans-serif; line-height: 20px;"><i style="background-color: white;">              {</i></span></span></div> <div> <span style="font-size: medium;"><span style="font-family: Trebuchet MS, sans-serif; line-height: 20px;"><i style="background-color: white;">                      </i></span></span></div> <div> <span style="font-size: medium;"><span style="font-family: Trebuchet MS, sans-serif; line-height: 20px;"><i style="background-color: white;">                        if(num<a[mid])</i></span></span></div> <div> <span style="font-size: medium;"><span style="font-family: Trebuchet MS, sans-serif; line-height: 20px;"><i style="background-color: white;">                           {</i></span></span></div> <div> <span style="font-size: medium;"><span style="font-family: Trebuchet MS, sans-serif; line-height: 20px;"><i style="background-color: white;">                                  end=mid-1;</i></span></span></div> <div> <span style="font-size: medium;"><span style="font-family: Trebuchet MS, sans-serif; line-height: 20px;"><i style="background-color: white;">            </i></span></span></div> <div> <span style="font-size: medium;"><span style="font-family: Trebuchet MS, sans-serif; line-height: 20px;"><i style="background-color: white;">                           }</i></span></span></div> <div> <span style="font-size: medium;"><span style="font-family: Trebuchet MS, sans-serif; line-height: 20px;"><i style="background-color: white;">                        else</i></span></span></div> <div> <span style="font-size: medium;"><span style="font-family: Trebuchet MS, sans-serif; line-height: 20px;"><i style="background-color: white;">                           {</i></span></span></div> <div> <span style="font-size: medium;"><span style="font-family: Trebuchet MS, sans-serif; line-height: 20px;"><i style="background-color: white;">                              beg=mid+1;</i></span></span></div> <div> <span style="font-size: medium;"><span style="font-family: Trebuchet MS, sans-serif; line-height: 20px;"><i style="background-color: white;">                           } </i></span></span></div> <div> <span style="font-size: medium;"><span style="font-family: Trebuchet MS, sans-serif; line-height: 20px;"><i style="background-color: white;">                           mid=int((beg+end)/2) ;</i></span></span></div> <div> <span style="font-size: medium;"><span style="font-family: Trebuchet MS, sans-serif; line-height: 20px;"><i style="background-color: white;">              } </i></span></span></div> <div> <span style="font-size: medium;"><span style="font-family: Trebuchet MS, sans-serif; line-height: 20px;"><i style="background-color: white;">              </i></span></span></div> <div> <span style="font-size: medium;"><span style="font-family: Trebuchet MS, sans-serif; line-height: 20px;"><i style="background-color: white;">           if(a[mid]==num)   </i></span></span></div> <div> <span style="font-size: medium;"><span style="font-family: Trebuchet MS, sans-serif; line-height: 20px;"><i style="background-color: white;">               cout<<"Element Matched at index"<<p[mid]<<"\t[where first element at 0 index]";</i></span></span></div> <div> <span style="font-size: medium;"><span style="font-family: Trebuchet MS, sans-serif; line-height: 20px;"><i style="background-color: white;">           else</i></span></span></div> <div> <span style="font-size: medium;"><span style="font-family: Trebuchet MS, sans-serif; line-height: 20px;"><i style="background-color: white;">              cout<<"Element is not in List\n";</i></span></span></div> <div> <span style="font-size: medium;"><span style="font-family: Trebuchet MS, sans-serif; line-height: 20px;"><i style="background-color: white;">             getch();</i></span></span></div> <div> <span style="font-size: medium;"><span style="font-family: Trebuchet MS, sans-serif; line-height: 20px;"><i style="background-color: white;">   }    </i></span></span><br /> <span style="font-family: Trebuchet MS, sans-serif;"><span style="font-size: medium;"><span style="line-height: 20px;"><i style="background-color: white;"><br /></i></span></span> </span><br /> <h2 style="text-align: left;"> <span style="font-family: Trebuchet MS, sans-serif; font-size: large; line-height: 20px;">Output:</span></h2> <h2 style="text-align: left;"> <a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhJG9ibMjyytBTVbv0T4D51nYEI_sH0_s_et1s0vCO3qrEA7kr3x1-DZ1WFg3Br7N8XPeP_gC2mmC7lihzWhyphenhyphentL1hHe6v91KjcpH4ICIfd2kAWVN3wk1sZvqbLbQbvr7jS0IgObjcOCu_jx/s1600/bs.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><span style="font-family: Trebuchet MS, sans-serif;"><img border="0" height="216" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhJG9ibMjyytBTVbv0T4D51nYEI_sH0_s_et1s0vCO3qrEA7kr3x1-DZ1WFg3Br7N8XPeP_gC2mmC7lihzWhyphenhyphentL1hHe6v91KjcpH4ICIfd2kAWVN3wk1sZvqbLbQbvr7jS0IgObjcOCu_jx/s640/bs.jpg" width="640" /></span></a><span style="font-size: medium;"><span style="font-family: Trebuchet MS, sans-serif; line-height: 20px;"><i style="background-color: white;"> </i></span></span></h2> <h2 style="text-align: left;"> <span style="background-color: white; color: lime; font-family: Trebuchet MS, sans-serif; font-size: medium; line-height: 20px;"> </span></h2> <h2 style="text-align: left;"> <span style="background-color: white; font-family: Trebuchet MS, sans-serif; font-size: medium; line-height: 20px;"><br /></span></h2> <h2 style="text-align: left;"> <span style="background-color: white; font-family: Trebuchet MS, sans-serif; font-size: medium; line-height: 20px;"><br /></span></h2> <h2 style="text-align: left;"> <span style="background-color: white; font-family: Trebuchet MS, sans-serif; font-size: medium; line-height: 20px;"><br /></span></h2> <h2 style="text-align: left;"> <span style="background-color: white; font-family: Trebuchet MS, sans-serif; font-size: medium; line-height: 20px;"><br /></span></h2> <h2 style="text-align: left;"> <span style="background-color: white; font-family: Trebuchet MS, sans-serif; font-size: medium; line-height: 20px;"><br /></span></h2> <h2 style="text-align: left;"> <span style="background-color: white; font-family: Trebuchet MS, sans-serif; font-size: large; line-height: 20px;">Complexity:</span></h2> </div> <div style="background-color: white;"> <div style="font-weight: bold; text-align: left;"> <span style="font-size: medium;"><span style="font-family: Trebuchet MS, sans-serif; line-height: 20px;">Complexity is measured by number of comaparisons.So here we divide array in half after each comparison.So we can write</span></span></div> <div style="font-weight: bold; text-align: left;"> <span style="font-family: Trebuchet MS, sans-serif; font-size: medium; line-height: 20px;">                                           2^f(n)>n</span></div> <div style="font-weight: bold; text-align: left;"> <span style="font-family: Trebuchet MS, sans-serif;"><span style="color: lime; font-size: medium; line-height: 20px;">     </span><span style="font-size: medium; line-height: 20px;">               after  taking log on both side(with Base 2)-</span></span></div> <div style="font-weight: bold; text-align: left;"> <span style="font-family: Trebuchet MS, sans-serif; font-size: medium; line-height: 20px;">                                      f(n)log2=logn</span></div> <div style="font-weight: bold; text-align: left;"> <span style="font-family: Trebuchet MS, sans-serif; font-size: medium; line-height: 20px;">                                       f(n)=logn.</span></div> <h3 style="text-align: left;"> <span style="font-family: Trebuchet MS, sans-serif; font-size: large; line-height: 20px;">Limitations:</span></h3> <div style="font-weight: bold; text-align: left;"> <span style="font-family: Trebuchet MS, sans-serif; font-size: medium; line-height: 20px;">There are 2 requirements  of Binary search :</span></div> <div style="font-weight: bold; text-align: left;"> <span style="font-family: Trebuchet MS, sans-serif; font-size: medium; line-height: 20px;">1.Array must be sorted.</span></div> <div style="font-weight: bold; text-align: left;"> <span style="font-family: Trebuchet MS, sans-serif; font-size: medium; line-height: 20px;">2.One must have direct access to its middle element in any sublist.</span></div> <div style="font-weight: bold; text-align: left;"> <span style="font-family: Trebuchet MS, sans-serif; font-size: medium; line-height: 20px;"><br /></span></div> <div style="font-weight: bold; text-align: left;"> <span style="font-family: Trebuchet MS, sans-serif; font-size: medium; line-height: 20px;">In this situation,we will use linked list or Binary Search tree for store Data.</span></div> <div style="font-weight: bold; text-align: left;"> <span style="font-family: Trebuchet MS, sans-serif;"><span style="font-size: medium; line-height: 20px;">                                   </span><span style="color: lime; font-size: medium; line-height: 20px;">             </span><span style="font-size: medium; line-height: 20px;">           </span></span></div> </div> <div style="background-color: white; font-weight: bold;"> <span style="font-size: medium;"><span style="font-family: Trebuchet MS, sans-serif; line-height: 20px;">                       </span></span></div> <div style="background-color: white; font-weight: bold;"> <span style="font-size: medium;"><span style="font-family: Trebuchet MS, sans-serif; line-height: 20px;">     </span></span></div> <div style="background-color: white; font-weight: bold;"> <span style="background-color: transparent; color: red; font-family: 'Trebuchet MS', sans-serif; font-size: large; font-weight: normal;">If you want to share more information about topic discussed above or find anything incorrect Please do comments. </span></div> </div> </h2> <h2> <div style="text-align: left;"> <div style="background-color: white; font-weight: bold;"> </div> <div style="background-color: white; font-weight: bold;"> <span style="font-size: medium;"><span style="font-family: Trebuchet MS, sans-serif; line-height: 20px;"><br /></span></span></div> <div style="background-color: white; font-size: 13.5pt; font-weight: bold; line-height: 115%;"> <br /></div> <div style="font-weight: bold;"> </div> </div> </h2> </div>

Program For Binary Search[How to]

                                    Binary Search    Goal-- How to do Binary Search In a Given Array?    Method Used-- Divide and...

+ Read more »