Data Structures Practical 4
Question 1
Write a program to find the first and last occurrence of the element 3 in an array of 20 integers using binary search.
occurance.c
C
#include <stdio.h>
#include <conio.h>
void main()
{
int arr[20] = {1, 2, 2, 3, 3, 3, 3, 3, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16};
int target = 3;
int low, high, mid, i;
int firstOccurrence = -1;
int lastOccurrence = -1;
clrscr();
printf("\nArray elements are:\n");
for(i = 0; i < 20; i++)
printf("%d ",arr[i]);
low = 0;
high = 19;
while (low <= high)
{
mid = (low + high) / 2;
if (arr[mid] == target)
{
firstOccurrence = mid;
high = mid - 1;
}
else if (target < arr[mid])
{
high = mid - 1;
}
else {
low = mid + 1;
}
}
low = 0;
high = 19;
while (low <= high)
{
mid = (low + high) / 2;
if (arr[mid] == target)
{
lastOccurrence = mid;
low = mid + 1;
}
else if (target < arr[mid])
{
high = mid - 1;
}
else {
low = mid + 1;
}
}
printf("\nTarget Element to search: %d", target);
if (firstOccurrence != -1)
{
printf("\nFirst occurrence is at Position %d",firstOccurrence + 1);
printf("\nLast occurrence is at Position %d",lastOccurrence + 1);
}
else
{
printf("\nElement %d was not found in the array.", target);
}
getch();
}
Output
Question 2
Given an array of 15 integers, write a program to find the two middle elements using binary search.
twomiddle.c
C
#include <stdio.h>
#include <conio.h>
void main()
{
int arr[15] = {10, 14, 19, 26, 27, 31, 33, 35, 42, 44, 50, 55, 60, 65, 70};
int low, high, mid, i;
int firstMiddle = -1, secondMiddle = -1;
clrscr();
printf("\nArray elements are:\n");
for(i = 0; i < 15; i++)
printf("%d ",arr[i]);
low = 0;
high = 14;
while (low <= high) {
mid = (low + high) / 2;
if (mid == 6) {
firstMiddle = arr[mid];
break;
}
else if (mid > 6) {
high = mid - 1;
}
else {
low = mid + 1;
}
}
low = 0;
high = 14;
while (low <= high) {
mid = (low + high) / 2;
if (mid == 7) {
secondMiddle = arr[mid];
break;
}
else if (mid > 7) {
high = mid - 1;
}
else {
low = mid + 1;
}
}
printf("\nFirst Middle Element At Position 7: %d\n", firstMiddle);
printf("\nSecond Middle Element At Position 8: %d\n", secondMiddle);
getch();
}
Output
