Instructions In your sequential_search function, simply scan through the array a
ID: 3909270 • Letter: I
Question
Instructions
In your sequential_search function, simply scan through the array and compares each array element with the value you want to search. If a match occurs the index of the matched element will be returned. If no match is found after the full scan, -1 will be returned.
In your binary_search function, considers the element at the middle of the array where middle = (left + right) / 2. The variable left and right store the left and right index that defines the current section of the array that may contain your toSearch value. At the first round, when you are looking at the whole array, left is 0 and right is size - 1. It then determines if the value of the middle element in section of the array is greater, less, or equal to toSearch value. If it is equal to toSearch, the value has been found and the index location is returned. If it is greater than toSearch, your toSearch may be located in the left half of the current section, then your left will stay same and your right will be changed to the position on the left next to the middle. If the value is less than toSearch, your toSearch may be located in the right half of the current section, then your left should be changed to the the position on the right next to the middle and your right will stay same. This process of halving the array and looking at the middle element is repeated until the element is found or not located in any of the position tested (when left is greater than right). Below is some pseudo code for this logic:
The main program initializes an array of 10 values in ascending order and a value to search (make your numbers). The two search function should be called respectively and the result be displayed using the following format depending on the location.
The value of s has been found at location l in the array. Or The value of s is not present in the array. Replace s and l with the value to search and the index (if found).
You may start with the array value as {1, 4, 6, 18, 33, 56, 64, 71, 99, 102} and set value to search to 64 to try.
Sample run 1 (searching 64):
Sample run 2 (searching 60, not present in array):
Development information
Try to develop on your PC first. Make sure the program will compile and give the expected output.
Copy the code to this page and try to run it.
Submit the code. If it cannot pass all test cases, tweak your code for formatting. If you do not understand the error message, rather than stuck on the error message, you rather try to do a code inspection visually to look for errors.
Explanation / Answer
PROGRAM
#include<iostream>
using namespace std;
// implement binarySearch() function with 3 parameters
int binarySearch(int x[],int size,int key)
{
int mid,left,right; // declare 3 integer variables
left=0; // initialize left=0
right=size-1; // intialize right=(total elements in the array - 1)
while(left<=right) // create while loop until total elements in the array
{
mid=(left+right)/2; // calculate mid element in the array
if(key==x[mid]) // check search element = mid element
return mid; // then, return position of element
else
if(key>x[mid]) // else, check key>mid element
left=mid+1; // increment of mid position and assign to left
else
right=mid-1; // else, decrement of mid position and assign to rifht
}
return -1; // there is no element then, return -1
}
// implement sequentialSearch() function with 3 parameters
int sequentialSearch(int x[],int size,int key)
{
for(int i=0;i<size;i++) // create for loop until total elements in the array
{
if(x[i]==key) // check array of elements = key
return(i); // then, return position of element
}
return -1; // there is no element then, return -1
}
int main()
{
int x[]={1,4,6,18,33,56,64,71,99,102}; // declare constant array of integer elements
int k,s,s1; // declare integer variables
cout<<"Enter Searching Element: "; cin>>k; // reading searching element k
s=binarySearch(x,10,k); // calling binarySearch() function and return value receive into s
s1=sequentialSearch(x,10,k); // calling sequentialSearch() function and return value receive into s1
if(s!=-1) // check s not = -1 (binarySearch())
cout<<" The value of "<<k<<" has been found at location "<<s<<" in the array."; // then, display this message
else
cout<<" The value of "<<k<<" is not present in the array."; // else, display this message
if(s1!=-1) // check s1 not = -1 (sequentialSearch())
cout<<" The value of "<<k<<" has been found at location "<<s<<" in the array."; // then, display this message
else
cout<<" The value of "<<k<<" is not present in the array."; // else, display this message
return 0;
}
OUTPUT-1
Enter Searching Element: 64
The value of 64 has been found at location 6 in the array.
The value of 64 has been found at location 6 in the array.
OUTPUT-2
Enter Searching Element: 60
The value of 60 is not present in the array.
The value of 60 is not present in the array.
OUTPUT-3
Enter Searching Element: 99
The value of 99 has been found at location 8 in the array.
The value of 99 has been found at location 8 in the array.
OUTPUT-4
Enter Searching Element: 199
The value of 199 is not present in the array.
The value of 199 is not present in the array.