Comparison/Steps in Linear Search Vs Binary Search

Lab-1: Comparison/Steps in Linear Search Vs Binary Search (2 marks):

Compare number of comparisons/steps taken by linear search and binary search in a sorted array to search an element. C file is given below. Put your java code after that.

·        Take an array of size 1000

·        Take 1000 integers as input in the array as sorted. Take A[i] = 2*i. It will make the array sorted

·        Take an integer as input as a search value “key”

·        Search the “key” in the array linearly and count the number of comparisons taken by the linear search

·        Search the “key” again in the array by binary search and count the number of comparisons taken by the binary search

·        Run the above two searching again and again for 10 times for 10 different keys given as follows and record the number of comparisons taken by linear search and binary search in the following table

C File:

#include

#define ARRAY_SIZE 1000		// Size of the array

int key;
int A[ARRAY_SIZE];			// one dimensional array of size ARRAY_SIZE
int count_linear_search;		// counter for number of comparison in linear search
int count_binary_search;		// counter for number of comparison for binary search

void take_input_A(void)
{
	int i;
	for(i=0; i<ARRAY_SIZE; i++)
	{
		A[i] = 2*i;			// this entry will make A sorted (0, 2, 4, 6, ..., 1998)
	}
}

void search_A_linear(void)			// search the array linearly from 0 to ARRAY_SIZE - 1
{
	int i;
	count_linear_search = 0;		// count the number of comparison for linear search. Start from 0
	for(i=0; i<ARRAY_SIZE; i++)		// go gradually from 0 to ARRAY_SIZE-1
	{
		count_linear_search++;	// count the number of comparison for linear search
		if(A[i] >= key)
			break;		// if found or bigger, then get out of the loop
	}
}


void search_A_binary(void)			// search the array by binary search, as the array is sorted
{
	int i, mid, first, last;
	
	first = 0;
	last = ARRAY_SIZE-1;
	
	count_binary_search = 0;		// count the number of comparison for binary search. Start from 0
	while((first<=last)))			// Array size is 1 or more, so binary search can be applied. Otherwise terminate
	{
		count_binary_search++;	// count the number of comparison for binary search
		mid = (last+first)/2;		// find the middle position
		if(key == A[mid])		// check if the key is in middle position
			return;		// if found, then return, no need to proceed any more
		if(key > A[mid])		// if not found, then see if the key is bigger than the middle position
			first = mid+1;	// if bigger, then key can be available in the right side (not left side). 
					// So, make the array as left half by taking the firt as middle+1, last remains same
		else 
			last = mid-1;	// else, key can be in the left side (not right side). 
					// So, make the array left half by taking last as middle-1, first remains same
	}
}


void main(void)
{
	int i;
	take_input_A();			// call the function to take sorted input in array A
	printf("\nEnter a value to search: ");	// take the key as input from the user
	scanf("%d", &key);
	search_A_linear();			// do linear search
	search_A_binary();			// do binary search
	printf("\nNumber of comparison for linear search: %d, binary search: %d\n", count_linear_search, count_binary_search);
					// print how many comparisons are needed for linear search and binary search
}