Comparison/Steps in Linear Search Vs Binary Search

خوارزميات
برمجة

2021-09-12
adnandsibai

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

Key	0	1998	2000	1000	502	122	1498	498	4	8
Number of comparisons taken by Linear search
Number of comparisons taken by Binary search

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
}

الأجوبة

Key	0	1998	2000	1000	502	122	1498	498	4	8
Number of comparisons taken by Linear search	1	1000	1000	501	252	62	750	250	3	5
Number of comparisons taken by Binary search	9	10	10	9	10	4	2	2	8	9

java file:

import java.util.Scanner;

public class Main
{
    final static int ARRAY_SIZE =1000;		// Size of the array
    static int key;
    static int []A=new int[ARRAY_SIZE];			// one dimensional array of size ARRAY_SIZE
    static int count_linear_search;		// counter for number of comparison in linear search
    static int count_binary_search;		// counter for number of comparison for binary search
    
    
    static void take_input_A()
    {
	int i;
	for(i=0; i<ARRAY_SIZE; i++)
	{
		A[i] = 2*i;			// this entry will make A sorted (0, 2, 4, 6, ..., 1998)
	}
    }
    
    static void search_A_linear()			// 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
	}
        
    }
    
    static void search_A_binary()			// 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
	}
        
    }
	public static void main(String[] args) {
			int i;
			take_input_A();			// call the function to take sorted input in array A
			System.out.println("\nEnter a value to search: ");	// take the key as input from the user
			Scanner input=new Scanner(System.in);
			key=input.nextInt();
			search_A_linear();			// do linear search
			search_A_binary();			// do binary search
			System.out.println("\nNumber of comparison for linear search: "+count_linear_search+", binary search: "+count_binary_search+"\n");
					// print how many comparisons are needed for linear search and binary search
	}
}

سجل الدخول لتستطيع الإجابة

هل كان المحتوى مفيد؟

0 نعم

0 لا

أسئلة مشابهة

لايوجد أسئلة حاليا

القوائم الدراسية التي ينتمي لها السؤال

لايوجد قوائم حاليا

معلومات ذات صلة

تبحث عن مدرس اونلاين؟

ابحث عن مدرسك