1. Consider the following specification: Define a function find which satisfies
ID: 3830628 • Letter: 1
Question
1. Consider the following specification: Define a function find which satisfies the following claim: If x is an integer and xs is a sequence of integers, find(x,xs) is the index position of the first occurrence of x in xs (or 1 if x 6 xs). What algorithm would you use and why?
2. Implement the function find from Problem 4.
3. What algorithm would you choose to solve Problem 4, if xs was a sorted sequence?
Binary Search
4. Implement a recursive definition of the function find given the assumption that xs is now a sorted sequence.
Explanation / Answer
#include <stdio.h>
//main function
int main(){
//sequence of integers
int xs[]={4,3,5,2,2,2,4,5,2,4,1,2,2,3,4,5,3,5,12};
//size of array
int size=sizeof(xs)/sizeof(int);
//x value
int x=5;
int i;
int result=-1;
for(i=0;i<size;i++){
//x found in xs
if(xs[i]==x){
result=i;
break;
}
}
printf("%d",result);
}
output:2
3)When it is sorted array then it is better choose binary search it takes o(logn) time
#include <stdio.h>
/* if x is present in arr[] then returns the index of
FIRST occurrence of x in arr[0..n-1], otherwise
returns -1 */
int first(int arr[], int low, int high, int x, int n)
{
if(high >= low)
{
int mid = low + (high - low)/2;
if( ( mid == 0 || x > arr[mid-1]) && arr[mid] == x)
return mid;
else if(x > arr[mid])
return first(arr, (mid + 1), high, x, n);
else
return first(arr, low, (mid -1), x, n);
}
return -1;
}
//main function
int main(){
//sequence of integers
int xs[]={1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,4,5,5,7,8};
//size of array
int size=sizeof(xs)/sizeof(int);
//x value
int x=3;
printf("%d",first(xs,0,size-1,x,size));
}
output: 7
1)When array is not sorted it is etter to choose simple liner search.It takes o(n) time#include <stdio.h>
//main function
int main(){
//sequence of integers
int xs[]={4,3,5,2,2,2,4,5,2,4,1,2,2,3,4,5,3,5,12};
//size of array
int size=sizeof(xs)/sizeof(int);
//x value
int x=5;
int i;
int result=-1;
for(i=0;i<size;i++){
//x found in xs
if(xs[i]==x){
result=i;
break;
}
}
printf("%d",result);
}
output:2
3)When it is sorted array then it is better choose binary search it takes o(logn) time
#include <stdio.h>
/* if x is present in arr[] then returns the index of
FIRST occurrence of x in arr[0..n-1], otherwise
returns -1 */
int first(int arr[], int low, int high, int x, int n)
{
if(high >= low)
{
int mid = low + (high - low)/2;
if( ( mid == 0 || x > arr[mid-1]) && arr[mid] == x)
return mid;
else if(x > arr[mid])
return first(arr, (mid + 1), high, x, n);
else
return first(arr, low, (mid -1), x, n);
}
return -1;
}
//main function
int main(){
//sequence of integers
int xs[]={1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,4,5,5,7,8};
//size of array
int size=sizeof(xs)/sizeof(int);
//x value
int x=3;
printf("%d",first(xs,0,size-1,x,size));
}
output: 7
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.