Practical 1

Set A

a) Create a random array of n integers. Accept a value x from user and use linear search algorithm to
check whether the number is present in the array or not and output the position if the number is
present.

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

void generateRandomArray(int arr[], int n)

srand(time(0));

for (int i = 0; i < n; i++)

arr[i] = rand() % 100;

int linearSearch(int arr[], int n, int x)

for (int i = 0; i < n; i++)

if (arr[i] == x)

return i;

return -1;

int main()

int n, x, position;

printf("Enter the size of the array: ");

scanf("%d", &n);
int arr[i];

generateRandomArray(arr, n);

printf("Generated array: ");

for (int i = 0; i < n; i++)

printf("%d ", arr[i]);

printf("\n");

printf("Enter the number to search for: ");

scanf("%d", &x);

position = linearSearch(arr, n, x);

if (position != -1)

printf("Number %d is found at position %d (index %d).\n", x, position + 1, position);

else

printf("Number %d is not found in the array.\n", x);

return 0;

}
b) Accept n values in array from user. Accept a value x from user and use sentinel linear search
algorithm to check whether the number is present in the array or not and output the position if the
number is present.

 #include <stdio.h>

#include <stdlib.h>

int linear(int[], int, int);

void main()

int *arr;

int i, n, k, index;

printf("Enter the number of elements in the array:\n");

scanf("%d", &n);

arr = (int*)malloc(sizeof(int));

printf("Enter %d elements of the array:\n", n);

for (i = 0; i < n; i++)

scanf("%d", &arr[i]);

printf("Enter the element to be searched:\n");

scanf("%d", &k);

index = linear(arr, n, k);

if (index == 0)

printf("Element %d is not present in the array\n", k);

else

printf("Element %d is present at location %d in the array\n", k, index + 1);

int linear(int array[], int size, int num)

for (int i = 0; i < size; i++)

if (num == array[i])
return i;

}
c) Accept n sorted values in array from user. Accept a value x from user and use binary search
algorithm to check whether the number is present in sorted array or not and output the position if
the number is present.

#include <stdio.h>

#include <stdlib.h>

int binary(int[], int, int);

void main()

int *arr;

int i, n, k, index;

printf("Enter the number of elements in the array:\n");

scanf("%d", &n);

arr = (int*)malloc(sizeof(int));

printf("Enter %d elements of the array in the sorted format:\n", n);

for (i = 0; i < n; i++)

scanf("%d", &arr[i]);

printf("Enter the element to be searched:\n");

scanf("%d", &k);

index = binary(arr, n, k);

if (index == 0)

printf("Element %d is not present in the array\n", k);

else

printf("Element %d is present at location %d in the array\n", k, index + 1);

int binary(int array[], int size, int num)

int i=0,j=size,k;

while(i<=j)

k=(i+j)/2;

if(array[k] == num)

return(k);
else if(array[k]<num)

i=k+1;

else

j=k-1;

Set B
a) Read the data from file 'cities.txt' containing names of cities and their STD codes. Accept a name of
the city from user and use linear search algorithm to check whether the name is present in the file
and output the STD code, otherwise output “city not in the list”.

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#define MAX_LINE_LENGTH 100

#define MAX_CITY_LENGTH 50

int searchCity(char *filename, char *city)

FILE *file = fopen(filename, "r");

char line[MAX_LINE_LENGTH];

char cityName[MAX_CITY_LENGTH];

int stdCode;

if (file == NULL)

printf("Error: Could not open file %s\n", filename);

return -1;

while (fgets(line, sizeof(line), file))

scanf(line, "%s %d", cityName, &stdCode);

if (strcmp(cityName, city) == 0)
{

fclose(file);

return stdCode;

fclose(file);

return -1;

int main() {

char city[MAX_CITY_LENGTH];

int stdCode;

printf("Enter the name of the city: ");

scanf("%s", city);

stdCode = searchCity("cities.txt", city);

if (stdCode != -1)

printf("The STD code for %s is %d\n", city, stdCode);

else

printf("City not in the list\n");

return 0;

}
b) Read the data from file 'cities.txt' containing names of cities and their STD codes. Accept a name
of the city from user and use sentinel linear search algorithm to check whether the name is present
in the file and output the STD code, otherwise output “city not in the list”.

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#define MAX_CITY_LENGTH 50

#define MAX_LINE_LENGTH 100

typedef struct

char city[MAX_CITY_LENGTH];

int stdCode;

City;

int sentinelSearch(City cities[], int n, char *searchCity)

int i = 0;

City lastCity = cities[n - 1];

strcpy(cities[n - 1].city, searchCity);

while (strcmp(cities[i].city, searchCity) != 0)

i++;

strcpy(cities[n - 1].city, lastCity.city);

if (i < n - 1 || strcmp(lastCity.city, searchCity) == 0)

return cities[i].stdCode;

return -1;

int main()
{

FILE *file;

char searchCity[MAX_CITY_LENGTH];

City cities[MAX_LINE_LENGTH];

int n = 0;

char line[MAX_LINE_LENGTH];

int stdCode;

file = fopen("cities.txt", "r");

if (file == NULL)

printf("Error: Could not open file.\n");

return 1;

while (fgets(line, sizeof(line), file))

sscanf(line, "%s %d", cities[n].city, &cities[n].stdCode);

n++;

fclose(file);

printf("Enter the name of the city: ");

scanf("%s", searchCity);

stdCode = sentinelSearch(cities, n, searchCity);

if (stdCode != -1)

printf("The STD code for %s is %d\n", searchCity, stdCode);

else

printf("City not in the list\n");

return 0;

}
c) Read the data from file ‘sortedcities.txt’ containing sorted names of cities and their STD codes.
Accept a name of the city from user and use binary search algorithm to check whether the name is
present in the file and output the STD code, otherwise output “city not in the list”

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#define MAX_CITY_LENGTH 50

#define MAX_CITIES 100

struct City

char city[MAX_CITY_LENGTH];

int stdCode;

};

int binarySearch(struct City cities[], int n, char *searchCity)

int left = 0, right = n - 1;

while (left <= right)

int mid = (left + right) / 2;

int cmp = strcmp(cities[mid].city, searchCity);

if (cmp == 0)

return cities[mid].stdCode;

if (cmp < 0)

left = mid + 1;

else

right = mid - 1;

}
}

return -1;

int main()

FILE *file;

char searchCity[MAX_CITY_LENGTH];

struct City cities[MAX_CITIES];

int n = 0;

char line[100];

int stdCode;

file = fopen(“sortedcities.txt", "r");

while (fgets(line, sizeof(line), file))

scanf(line, "%s %d", cities[n].city, &cities[n].stdCode);

n++;

fclose(file);

printf("Enter the name of the city: ");

scanf("%s", searchCity);

stdCode = binarySearch(cities, n, searchCity);

if (stdCode != -1)

printf("The STD code for %s is %d\n", searchCity, stdCode);

else

printf("City not in the list\n");

return 0;

}
Set c

b) If the file contains multiple occurrences of a given element, will binary search output the position
of first occurrence or last occurrence?

 #include <stdio.h>

int FirstOccurrence(int arr[], int size, int target) {

int left = 0, right = size - 1;

int result = -1; // Default result if target is not found

while (left <= right) {

int mid = left + (right - left) / 2;

if (arr[mid] == target) {

result = mid; // Target found, continue to search in the left half

right = mid - 1; // Move to left side to find first occurrence

} else if (arr[mid] < target) {

left = mid + 1; // Move right

} else {

right = mid - 1; // Move left

return result;

int LastOccurrence(int arr[], int size, int target) {

int left = 0, right = size - 1;

int result = -1; // Default result if target is not found

while (left <= right) {

int mid = left + (right - left) / 2;

 if (arr[mid] == target) {

result = mid; // Target found, continue to search in the right half

left = mid + 1; // Move to right side to find last occurrence

} else if (arr[mid] < target) {

left = mid + 1; // Move right

} else {

right = mid - 1; // Move left

return result;

int main() {

// Example sorted array with multiple occurrences

int arr[] = {1, 2, 2, 2, 3, 4, 5, 5, 6, 7, 8};

int size = sizeof(arr) / sizeof(arr[0]);

int target = 2;

int firstOccurrence = findFirstOccurrence(arr, size, target);

int lastOccurrence = findLastOccurrence(arr, size, target);

if (firstOccurrence != -1) {

printf("First occurrence of %d is at index: %d\n", target, firstOccurrence);

} else {

printf("%d not found in the array.\n", target);

if (lastOccurrence != -1) {

printf("Last occurrence of %d is at index: %d\n", target, lastOccurrence);

} else {

printf("%d not found in the array.\n", target);

 }

return 0;

b) If the file contains multiple occurrences of a given element, will binary search output the position
of first occurence or last occurrence?

 #include <stdio.h>

#include <stdlib.h>

#include <time.h>

#define SIZE 10 // Array size for demonstration

// Function for Linear Search

int linearSearch(int arr[], int size, int target) {

for (int i = 0; i < size; i++) {

if (arr[i] == target) {

return i; // Target found

return -1; // Target not found

// Function for Sentinel Search

int sentinelSearch(int arr[], int size, int target) {

int last = arr[size - 1]; // Store the last element

arr[size - 1] = target; // Place the target at the end

int i = 0;

while (arr[i] != target) {

i++;
 }

// Restore the last element

arr[size - 1] = last;

// Check if the found index is valid

if (i < size - 1 || arr[size - 1] == target) {

return i; // Target found

return -1; // Target not found

// Function for Binary Search

int binarySearch(int arr[], int left, int right, int target) {

while (left <= right) {

int mid = left + (right - left) / 2;

// Check if target is present at mid

if (arr[mid] == target) {

return mid;

// If target is greater, ignore left half

if (arr[mid] < target) {

left = mid + 1;

} else { // If target is smaller, ignore right half

right = mid - 1;

return -1; // Target not found

}
// Function to compare and time the search algorithms

void testSearchAlgorithms(int arr[], int size, int target) {

clock_t start, end;

// Test Linear Search

start = clock();

int linearIndex = linearSearch(arr, size, target);

end = clock();

double linearTime = (double)(end - start) / CLOCKS_PER_SEC;

printf("\nLinear Search: Element %d found at index %d, Time : %f sec\n", target, linearIndex,
linearTime);

// Test Sentinel Search

start = clock();

int sentinelIndex = sentinelSearch(arr, size, target);

end = clock();

double sentinelTime = (double)(end - start) / CLOCKS_PER_SEC;

printf("\nSentinel Search: Element %d found at index %d, Time : %f sec\n", target, sentinelIndex,
sentinelTime);

// Test Binary Search (the array must be sorted)

start = clock();

int binaryIndex = binarySearch(arr, 0, size - 1, target);

end = clock();

double binaryTime = (double)(end - start) / CLOCKS_PER_SEC;

printf("\nBinary Search: Element %d found at index %d, Time : %f sec\n", target, binaryIndex,
binaryTime);

int main() {

// Example array for demonstration

 int arr[SIZE] = {20, 15, 30, 10, 5, 25, 35, 40, 50, 45};

// Sort the array for binary search

// Using a simple bubble sort for demonstration

for (int i = 0; i < SIZE - 1; i++) {

for (int j = 0; j < SIZE - i - 1; j++) {

if (arr[j] > arr[j + 1]) {

int temp = arr[j];

arr[j] = arr[j + 1];

arr[j + 1] = temp;

// Target value for search

int target = 20; // Best case for linear and sentinel search

printf("Searching for target value: %d\n", target);

// Test the search algorithms

testSearchAlgorithms(arr, SIZE, target);

return 0;

If the file contains multiple occurrences of a given element, linear search will give the Page 12 of 57
position of the first occurrence, what modifications are required to get the last occurrence?

 #include <stdio.h>

// Function to perform Linear Search to find the last occurrence

int LastOccurrence(int arr[], int size, int target) {

int lastIndex = -1; // Initialize to -1 to indicate not found

 for (int i = 0; i < size; i++) {

if (arr[i] == target) {

lastIndex = i; // Update the lastIndex whenever the target is found

return lastIndex; // Return the last occurrence index or -1 if not found

int main() {

// Example array with multiple occurrences

int arr[] = {1, 2, 3, 4, 2, 5, 2, 6, 7};

int size = sizeof(arr) / sizeof(arr[0]);

int target = 2; // The target we are searching for

int lastOccurrence = LastOccurrence(arr, size, target);

if (lastOccurrence != -1) {

printf("Last occurrence of %d is at index: %d\n", target, lastOccurrence);

} else {

printf("%d not found in the array.\n", target);

return 0;