Please type your question here: Note: the following program consists of using th
ID: 3761499 • Letter: P
Question
Please type your question here:
Note: the following program consists of using the language "SASM")
%include "io.inc"
; store in the buffer
; inc by 2 addresses since we are storing 16-bit words
; write the array data out to confirm it’s right
LENGTH
mov edx, 0
; set the registers as per the functions’s documentation ; write the results of the search
ret
; set the registers as per the functions’s documentation ; write the results of the search
; writes the results of a search
; assumptions:
; the value searched for is in ax (16-bit)
; the count into the array where found is returned in dx writeresults:
NEWLINE ret
; Sequential search routine
; assumptions:
; the array to be searched is in memory - pointed to in EBP
; the length of the array is in dx (16-bit)
; the value to search for is in ax (16-bit)
; when done, the count into the array where found is returned in dx ; the array is composed of 32-bit words
seqsearch:
; Binary search routine
; assumptions:
; the array to be searched is in memory - pointed to in EBP
; the length of the array is in dx (16-bit)
; the value to search for is in ax (16-bit)
; when done, the count into the array where found is returned in dx ; the array is composed of 32-bit words
binarysearch:
push ecx ; preserve the starting values push ebx ; of ebx and ecx
As you can see, the first part of the program creates an array of (in this case) 200 values, counting up by 5. These are stored as 16-bit words. It then writes out the values of the array to confirm that it’s working.
Then the program calls a couple of functions that perform searches: a sequential search and a binary search. Your task is to write these two functions.
A sequential search inspects each element of a list, in sequence, to see if it can find the value we are interested in. You can see that I have defined the “interface” for the function. It expects that when it’s called, we will have:
- the address of array to be searched in the EBP register
- the length of the array in dx (the 16-bit part of EDX)
- the value to search for in ax (the 16-bit part of EAX)
- when the function is done, the count into the array where the value was found is returned
in dx
A binary search is much faster but a little more complex. Assuming that the list is in ascending order, smallest to largest, whenever we look at a value in the list, we immediately know if the value that we are looking for is above or below the current value. A binary search works like this.
Set MIN to the start of the list
Set MAX to the end of the list
SRCHSTEP:
Set MID to the midway point in the list ( (MIN+MAX)/2)
Check the value at MID –if SRCH (the value we are looking for) is less than MID, then:
- it must be to the left
- set MAX to MID and go back to SRCHSTEP else if SRCH is greater than MID, then:
- it must be to the right
- set MIN to MID and go back to SRCHSTEP else if SRCH equals MID, we have found it!
If MIN and MAX are ever equal, then the value is not in the list.
Explanation / Answer
i didnt understand which launguage you want,am sending in c launguge implementation of both serching algorithams
#include <stdio.h>
//linear seach
void sequential_search(int a[], int size, int n)
{
int k;
for (k = 0; k < size; k++)
{
if (a[k] == n)
{
printf("%d found at location %d. ", n, k+1);
break;
}
}
if (k == size)
printf("Not found! %d is not present in the list. ", n);
}
//BINARY SEARCH
void binary_search(int a[], int size, int n)
{
int k, first, last, middle;
first = 0;
last = size - 1;
middle = (first+last) / 2;
while (first <= last)
{
if (a[middle] < n)
first = middle + 1;
else if (a[middle] == n)
{
printf("%d found at location %d. ", n, middle+1);
break;
}
else
last = middle - 1;
middle = (first + last) / 2;
}
if ( first > last )
printf("Not found! %d is not present in the list. ", n);
}
int main()
{
int ar[200], k, n, size;
printf("Enter the size of the list:");
scanf("%d", &size);
printf("Enter %d Integers in ascending order ", size);
for (k = 0; k < size; k++)
scanf("%d", &ar[i]);
printf("Enter value to find ");
scanf("%d", &n);
printf("linear search ");
sequential_search(ar, size, n);
printf("Binary search ");
binary_search(ar, size, n);
return 0;
}