in C++ Binary Search Description In this assignment you are requested to impleme
ID: 3748390 • Letter: I
Question
in C++
Binary Search Description In this assignment you are requested to implement the binary search algorithm You can assume that the input sequence is already sorted in ascending order. Input structure The test file represents one test case (tN-input, oN-correct output). The se- quences and the element to search are integers (i.e. you can safely store them into int variables). Each case starts with a number which is the number of integers in the sequence. The following number is the element to search. Then the elements of the sequence follow, one per line. You can assume that the input is correctly structured (i.e. no data are missing). Output structure All the searching algorithms must return -1 if a, is not in the sequence, or its position (i.e. array index) if it is contained. You can assume that all the numbers in the sequence are distinct.Explanation / Answer
PROGRAM
#include<iostream>
#include<cstdlib>
using namespace std;
// create binSearch() function
// with formal parameters are integer array a,size n and searching element key
int binSearch(int a[],int n,int key)
{
// declare integer variables and initialize first=0,last=n-1,mid
int first=0,last=n-1,mid;
while(first<=last) // create while loop until last element in the array
{
mid=(first+last)/2; // calculate mid element in the array
if(a[mid]>key) last=mid-1; // check mid>key then assign last=mid-1
else
if(a[mid]<key) first=mid+1; // check mid<key then assign first=mid+1
else
return mid+1; // return position of searching element
}
return -1; // return if not found seraching element
}
int main()
{
int a[100],n,key; // declare array a and n,key
cout<<"Enter Size of an Array: ";
cin>>n; // read size of an array
cout<<"Enter Sorted Elements"<<endl;
for(int i=0;i<n;i++)
cin>>a[i]; // reading sorted elements
cout<<"Enter Searching Element: ";
cin>>key; // enter searching element
int k=binSearch(a,n-1,key); // calling binSearch() function and return value into k
if(k==-1) // check k==-1
cout<<"Element is Not Found..."<<endl; // display not found
else
cout<<" Element is Found and Position is: "<<k; // else, display found with position
return 0;
}
OUTPUT-1
Enter Size of an Array: 5
Enter Sorted Elements
10 12 13 15 16
Enter Searching Element: 15
Element is Found and Position is: 4
OUTPUT-2
Enter Size of an Array: 5
Enter Sorted Elements
10 12 16 18 19
Enter Searching Element: 25
Element is Not Found...
OUTPUT-3
Enter Size of an Array: 10
Enter Sorted Elements
10 12 16 18 20 29 88 99 115 199
Enter Searching Element: 99
Element is Found and Position is: 8
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.