(c++ is the code used) Implement a function that searches for a given value k in

Question

(c++ is the code used) Implement a function that searches for a given value k in an array of integers. Do not assume the values are in order. If the value is found, the function returns the index of the value in the array; otherwise it returns -1. The following is a declaration of the function. int search(int a[], int size, int k) Write a function called binarySearch that finds an occurrence of an integer k in an array a using binary search where the integers in a form an increasing sequence. The function signature is given below. The function returns true if k is in a, otherwise it returns false. Do not use the search function available in the C++ standard library. bool binarySearch(int a[], int size, int k)

Explanation / Answer

1)

#include<iostream>
using namespace std;
int search(int a[],int size,int k)//method which searches for a value, in a given array if it is found, then return its index, else returns -1
{
   int i;
   for(i=0;i<size;i++)
   {
       if(a[i]==k)return i;//when found returning index
   }
  
   return -1;//when not found returning -1
}
int main()
{
   //testing..
   int a[10]={1,7,5,4,2,8,6,9,3,10};
   cout<<"Found at:"<<search(a,10,8)<<endl;
      
  
   return 0;
}

output:-

Found at :5

2)

#include<iostream>
using namespace std;

bool binarySearch(int a[],int size,int k)//this method search for a value k in given sorted list a, and returns true if value is present , otherwise returns false
{   int h,l,m;
   l=0;h=size;
   m=(l+h)/2;
  
   while(l<=h)
   {
       if(a[m]==k)return true;//if k is in a returning true  
       if(a[m]<k)
           l=m+1;
       else
           h=m-1;
           m=(l+h)/2;
   }  
  
   return false;//when not found returning false...
}

int main()
{
  
   int a[5]={1,2,3,4,5};
   cout<<"Found "<<binarySearch(a,5,2)<<endl;
   cout<<"Found "<<binarySearch(a,5,1)<<endl;
   cout<<"Found "<<binarySearch(a,5,3)<<endl;
   cout<<"Found "<<binarySearch(a,5,4)<<endl;
   cout<<"Found "<<binarySearch(a,5,5)<<endl;
   cout<<"Found "<<binarySearch(a,5,6)<<endl;
   cout<<"Found "<<binarySearch(a,5,0)<<endl;
   return 0;
}

output:

Found 1
Found 1
Found 1
Found 1
Found 1
Found 0
Found 0

//true value is printed as 1, and false value is printed as 0

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

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