Write a C++ program to implement the Binary Search algorithm for searching a tar

Question

Write a C++ program to implement the Binary Search algorithm for searching a target element in a sorted vector. Your program should keep track of the number of comparisons used to find the target. To ensure the correctness of the algorithm the input data should be sorted in ascending or descending order. An exception should be thrown when an input vector is unsorted. Test your program using vectors populated with consecutive (increasing or decreasing) integers in the ranges from 1 to powers of 2, that is, to these numbers: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048. Select the target as the last integer in the vector. Tabulate the number of comparisons to find the target in each range. Plot the number of comparisons to find a target where the vector size n = 2^k, k = 1, 2, ..., 11 in each increasing/decreasing case. You can use any graphical package (including a spreadsheet). Provide a mathematical forum la/function which takes n as an argument, where n is the vector size and returns as its value the number of comparisons. Does your formula match the computed output for a given input? Justify your answer. How can you modify your formula/function if the largest number in a vector is not an exact power of two? Test your program using input in ranges from 1 to 2^k - 1, k = 1, 2, 3, ..., 11. Use Big-O asymptotic notation to classify this algorithm and justify your answer.

Explanation / Answer

1> #include<bits/stdc++.h>
using namespace std;
int Binary_Search(vector <int> v,int l,int r,int target)
{
   int mid;
   if(l==r)
   {
   if(v[l]==target)
   return l;
   else return 0;
   }
  
   mid=(l+r+1)/2;
   if(v[mid]==target)
   return mid;
   else if(v[mid]>target)
   return Binary_Search(v,l,mid-1,target);
   else return Binary_Search(v,mid+1,r,target);
  
}
int main()
{
   int i;
   int postion;
   vector <int> v;
int size,n;
cout<<"Enter the Size of vector"<<endl;
  
   cin>>size;
   cout<<"Enter the Vector element"<<endl;
   for(i=0;i<size;i++)
   {
      cin>>n;
      v.push_back(n);
   }
   int taget_element;
   cout<<"Enter the target element"<<endl;
   cin>>taget_element;
   postion=Binary_Search(v,0,size,taget_element);
   if(postion)
   cout<<"Potion of element is :" <<postion;
   else cout<<"element not found"<<endl;
        
}

A : iImplement the function for checking given vector elements are sorted or not

if not then give some exception;

#include<bits/stdc++.h>
using namespace std;
int Binary_Search(vector <int> v,int l,int r,int target)
{
   int mid;
   if(l==r)
   {
   if(v[l]==target)
   return l;
   else return 0;
   }
  
   mid=(l+r+1)/2;
   if(v[mid]==target)
   return mid;
   else if(v[mid]>target)
   return Binary_Search(v,l,mid-1,target);
   else return Binary_Search(v,mid+1,r,target);
  
}
bool Sorted_or_not(vector <int> v,int n)
{
    int i;
    int c1=1,c2=1;
    for(i=1;i<n;i++)
    {
        if(v[i-1]>v[i])
        c1++;
        else c2++;
       
   }
  
   if(c1==n || c2==n)
   {
      return false;
   }
  
   else return true;
}
int main()
{
   int i;
   int postion;
   vector <int> v;
int size,n;
cout<<"Enter the Size of vector"<<endl;
  
   cin>>size;
   cout<<"Enter the Vector element"<<endl;
   for(i=0;i<size;i++)
   {
      cin>>n;
      v.push_back(n);
   }
   if(Sorted_or_not(v,size))
   {
           cout<<"Vector are not sorted please sort the vector"<<endl;
       exit;
   }
   else {
  
   int taget_element;
   cout<<"Enter the target element"<<endl;
   cin>>taget_element;
  
     
   postion=Binary_Search(v,0,size,taget_element);
   if(postion)
   cout<<"Potion of element is :" <<postion;
   else cout<<"element not found"<<endl;
}
        
}

B: in case of B we use any one give above program gives correct result;

C:

Tagent for

inc. value

#comparision for

inc. value

Taget for

decc. value

#comparision for

decc. value

Range[1,n]

Tagent for

inc. value

#comparision for

inc. value

Taget for

decc. value

#comparision for

decc. value

Result for the farmula for the 5 items [1,1] 1 1 1 1 [1,2] 2 1 1 1 [1,4] 4 2 1 2 [1,8] 8 3 1 3 [1,16] 16 4 1 4 [1,32] 32 5 1 5 [1,64] 64 6 1 6 [1,128] 128 7 1 7 [1,256] 256 8 1 8 [1,512] 512 9 1 9 [1,1024 1024 10 1 10 [1,2048] 2048 11 1 11

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.