DATE:……………………………. PAGE No……….
SEARCHING
AIM C Program to implement linear search technique
ALGORITHM
Begin
for i = 0 to (n - 1) by 1 do
if (a[i] = item) then
set loc = i
Exit
End if
End for
set loc = -1
End
ALGORITHM ANALYSIS
1. Time Complexity:
Best Case Average Case Worst Case
O(1) O(n) O(n)
2. Space Complexity: O(1)
Department of Computer Science and Engineering (Data
Science)
DATE:……………………………. PAGE No……….
PROGRAM
#include <stdio.h>
int main()
{
int array[100], search, i, n;
printf("Enter number of elements in array\n");
scanf("%d", &n);
printf("Enter %d integers :", n);
for (i = 0; i < n; i++)
scanf("%d", &array[i]);
printf("Enter a number to search\n");
scanf("%d", &search);
for (i = 0; i < n; i++)
{
if (array[i] == search) /* If required element is found */
{
printf("%d is present at location %d.\n", search, i+1);
break;
}
}
if (i == n)
printf("%d isn't present in the array.\n", search);
return 0;
}
Department of Computer Science and Engineering (Data
Science)
DATE:……………………………. PAGE No……….
AIM C Program to implement Binary search technique using iterative method
ALGORITHM
binarySearch(arr, size)
{
while(low<=high)
{
midIndex = (low + high)/2
if (item == arr[midIndex] )
return midIndex
else
if (item > arr[midIndex] )
low = midIndex + 1
else
high = midIndex –
}
}
ALGORITHM ANALYSIS
1. Time Complexity:
Best Case Average Case Worst Case
O(1) O(log n) O(log n)
2. Space Complexity: O(1)
Department of Computer Science and Engineering (Data
Science)
DATE:……………………………. PAGE No……….
PROGRAM
#include <stdio.h>
int binarySearch( int arr[], int item, int low, int high)
{
while (low <= high)
{
int midIndex = (low + high) / 2;
if (arr[midIndex] == item)
return midIndex;
else
if (arr[midIndex] > item)
low = midIndex + 1;
else
high = midIndex - 1;
}
return -1;
}
int main()
{
int array[100], search, i, n,result;
printf("Enter number of elements in array\n");
scanf("%d", &n);
printf("Enter %d integers :", n);
for (i = 0; i < n; i++)
scanf("%d", &array[i]);
printf("Enter a number to search\n");
scanf("%d", &search);
result = binarySearch(arr, search, 0, n - 1);
if (result == -1)
printf("Element not present");
else
printf("Element Present at index : %d", result);
return 0;
}
Department of Computer Science and Engineering (Data
Science)
DATE:……………………………. PAGE No……….
AIM C Program to implement Binary search technique using recursive method
ALGORITHM
binarySearch(arr, item, beg, end)
{
if (beg<=end)
midIndex = (beg + end) / 2
if (item == arr[midIndex])
return midIndex
else
if (item < arr[midIndex])
return binarySearch(arr, item, midIndex + 1, end)
else
return binarySearch(arr, item, beg, midIndex - 1)
return -1
}
ALGORITHM ANALYSIS
1. Time Complexity:
Best Case Average Case Worst Case
O(1) O(log n) O(log n)
2. Space Complexity: O(log n)
Department of Computer Science and Engineering (Data
Science)
DATE:……………………………. PAGE No……….
PROGRAM
#include <stdio.h>
int binarySearch(int arr[], int item, int beg, int end)
{
if (end >= beg)
{
int midIndex = (beg + end) / 2;
if (arr[midIndex] == item)
return midIndex;
if (arr[midIndex] < item)
return binarySearch(arr, item, beg, midIndex - 1);
else
return binarySearch(arr, item, midIndex + 1, end);
}
return -1;
}
int main()
{
int array[100], search, i, n,result;
printf("Enter number of elements in array\n");
scanf("%d", &n);
printf("Enter %d integers :", n);
for (i = 0; i < n; i++)
scanf("%d", &array[i]);
printf("Enter a number to search\n");
scanf("%d", &search);
result = binarySearch(arr, search, 0, n - 1);
if (result == -1)
printf("Element not present");
else
printf("Element Present at index : %d", result);
return 0;
}
Department of Computer Science and Engineering (Data
Science)
DATE:……………………………. PAGE No……….
PRACTICE PROBLEMS
PROBLEM-1
Given an array of a[]={65, 70, 75, 80, 85, 60, 55, 50, 45} to find an element 60 with the help of
searching techniques
PROGRAM
OUTPUT
Department of Computer Science and Engineering (Data
Science)
DATE:……………………………. PAGE No……….
PROBLEM-2
Given an array of a[]={-6,5,10,15,30,42,58,67} to find an element 42 with the help of
searching techniques.
PROGRAM
OUTPUT
Department of Computer Science and Engineering (Data
Science)
DATE:……………………………. PAGE No……….
PROBLEM-3
Given an array (17,24,6,-23,6,-23,10). 6 is present in the array display on screen “YES”
PROGRAM
OUTPUT
PROBLEM-4
Given an array (9,-5, 98, 32). 23 is not present in the array display on screen “NO”
PROGRAM
OUTPUT
PROBLEM-4
Using linear search determine the position of 8,1,99 and 44 in the list: [1,−2,32,8,17,19,42,13,0,44]
PROGRAM
OUTPUT
PROBLEM-5
Use the linear search program to search the key with value 8 in the list having duplicate values
such as [42,−2,32,8,17,19,42,13,8,44]. What is the position returned?
PROGRAM
OUTPUT
Department of Computer Science and Engineering (Data
Science)
DATE:……………………………. PAGE No……….
PROBLEM-6
Given a sorted array a[] with possibly duplicate elements, the task is to find indexes of the first and
last occurrences of an element x in the given array.( Example: a[]={1,3,5,5,5,5,67,123,125}, search
element x=5.)
PROGRAM
OUTPUT
Department of Computer Science and Engineering (Data
Science)
