I need a program in the language C with binary search given the conditions in th
ID: 3683377 • Letter: I
Question
I need a program in the language C with binary search given the conditions in the images. I am copying and pasting the sections of the code from the image below. Thank you!
int linSearch (int x[], int size, int target);
int binSearch (int x[], int size, int target);
int main(){
/* define arrays and target for search problem */
int a[18] = {3, 5, 7, 44, 12, 22, 33, 44, 55, 33,
-1, 9, 0, 3, 3, 4, 7, 5};
int aSize = 18;
int b[18] = {0, 1, 1, 1, 2, 5, 5, 6, 7,
9, 11, 14, 22, 33, 44, 44, 51, 53};
int bSize = 18;
int target;
int aLoc;
/* array a is not sorted */
/* use linear search */
aLoc = linSearch(a, aSize, target);
if (aLoc < aSize){
printf(“ target %d found at index %d.”, target, aLoc);
} else {
printf(“ target %d not found in array.”, target);
}
printf(“Enter a number that you would like to search for.”);
scanf(“%d”, &target);
/* array b is sorted */
/* use binary search */
int bLoc = binSearch(b, bSize, target);
if (bLoc < bSize){
printf(“ target %d found at index %d.”, target, bLoc);
} else {
printf(“ target %d not found in array.”, target);
}
return 0;
}
/* always keep target trapped between left and right */
int left = 0;
int right = size – 1;
while(left <= right){
int middle = (left + right) / 2;
if (x[middle] == target){ /* found it */
return middle;
}
if (x[middle] < target){
left = middle + 1; /* target on right side. Move in left end */
} else {
right = middle – 1; /* target on left side. Move in right end */
}
}
return size; /* target not here */
Many computer applications involve searching arrays to see if a targetelement is included in the array, and if so, where at. For example, considerthe array: 12 Note that element 12 is located at index 4. One often writes an array search function to search an array and report the location of the target element. The prototype ofa function for searching integer arrays would look something like this: ansearch (AR, x[], dnsize, target); This function would return the index ofthe array element that is equal to the target. There are two complications to deal with 1. What ifthe target is not in the array? It is probably NOT a good idea to have the search function write an error message, because this situation might occur 1,000,000 times each second, and would keep the user rather busy reading error messageS. A better way to deal with this is to return some number that is not a legal index. The calling program can examine the returned number, and deal with it according to if the returned number gives the location ofthe target, or the target was not found. The simplest invalid index to use is-1. But, it is better to avoid negative numbers, so 99% of the time, size is returned to indicate the target is not in the array. This is the first index past the valid index range for the array. Here is an example of how such a search function is used {3, 5, 7, 2, 12, 22, 33, 44, 55, 33, -1, 3, 0, 3, 3, 3, 4); a[] target: 44; an anlocation= search (a, 17, target); (location size Rzantil." tatge %d found at index d.", target, location); else [ Rain ," tatges d not found in ar ray.", target) ; 2. The other issue is what if the target occurs in more than one place? Usually we don't really care, and just return the index of the first place the target occurs. For one thing, this strategy is obviously the fastest thing to do. There are two basic types of searching; linear search and binary search. Linear search is easy to program and works on any array. Linear search basically walks through the array and checks each array element to see if it is the target. If it is the target, immediately return the index where the target was found. If you get to the end ofthe array without finding the target, return the size of the array Binary search only works ifthe data in the array is in order, and is a bit harder to program. But, it is a lot faster. It will be discussed below Here isan easy first look at algorithm analysis, which basically means analyzing how fast certain computer algorithms Data size The size of the data set is usually indicated by the letterm. For arrays, n is the size of the arrayExplanation / Answer
#include<stdio.h>
int linSearch (int x[], int size, int target);
int binSearch (int x[], int size, int target);
int main(){
/* define arrays and target for search problem */
int a[18] = {3, 5, 7, 44, 12, 22, 33, 44, 55, 33,
-1, 9, 0, 3, 3, 4, 7, 5};
int aSize = 18;
int b[18] = {0, 1, 1, 1, 2, 5, 5, 6, 7,
9, 11, 14, 22, 33, 44, 44, 51, 53};
int bSize = 18;
int target;
int aLoc;
/* array a is not sorted */
/* use linear search */
aLoc = linSearch(a, aSize, target);
if (aLoc < aSize){
printf(" target %d found at index %d.", target, aLoc);
} else {
printf(" target %d not found in array.", target);
}
printf(" Enter a number that you would like to search for.");
scanf("%d", &target);
/* array b is sorted */
/* use binary search */
int bLoc = binSearch(b, bSize, target);
if (bLoc < bSize){
printf(" target %d found at index %d.", target, bLoc);
} else {
printf(" target %d not found in array.", target);
}
return 0;
}
int binSearch (int arr[], int size, int target){
int left = 0;
int right = size -1;
while(left <= right){
int middle = (left + right) / 2;
if( ( middle == 0 || target > arr[middle-1]) && arr[middle] == target){ /* found first occurence of target */
return middle;
}
if (arr[middle] < target){
left = middle + 1; /* target on right side. Move in left end */
} else {
right = middle -1; /* target on left side. Move in right end */
}
}
return -1; // return -1, if not found
} /* target not here */
// Linearly search x in arr[]. If target is present then return its
// location, otherwise return -1
int linSearch(int arr[], int size, int target)
{
int i;
for (i=0; i<size; i++)
if (arr[i] == target)
return i;
return -1;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.