PROGRAMMING FOR

PROBLEM SOLVING --
PPS
SUBJECT CODE-
BTPS-101-18
By
[Link],AP,Chandigarh
Engineering College
PPS SYLLABUS
Unit 4
Basic Algorithms (6 lectures)
Searching, Basic Sorting Algorithms (Bubble, Insertion and
Selection), Finding roots of equations, notion of order of complexity
through example programs (no formal definition required)

By [Link],AP,Chandigarh Engineering
College
2
 Searching
➢ The process used to find the location of a target among a list of objects
➢ Searching an array finds the index of first element in an array containing
that value

3
4
5
 Unordered Linear Search
▸ Search an unordered array of integers for a value and return its index if the
value is found. Otherwise, return -1.
▸ A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7]

14 2 10 5 1 3 17 2
▸ Algorithm:
Start with the first array element (index 0)
while(more elements in array){
if value found at current index, return index;
Try next element (increment index);
}Value not found, return -1; By [Link],AP,Chandigarh Engineering College
6
 Unordered Linear Search
// Searches an unordered array of integers
int search(int data[], //input: array
int size, //input: array size
int value){ //input: search value
// output: if found, return index;
// otherwise, return –1.
for(int index = 0; index < size; index++){
if(data[index] == value)
return index;
} return -1;}
By [Link],AP,Chandigarh Engineering College
7
 Linear Search Algorithm
▸ LINEAR_SEARCH(A, N, VAL)
▸ Step 1: [INITIALIZE] SET POS = -1 Step 2: [INITIALIZE] SET I = 1
▸ Step 3: Repeat Step 4 while I<=N
▸ Step 4: IF A[I] = VAL
▸ SET POS = I
▸ PRINT POS
▸ Go to Step 6
▸ [END OF IF]
▸ SET I = I + 1
▸ [END OF LOOP]
▸ Step 5: IF POS = –1
▸ PRINT VALUE IS NOT PRESENT IN THE ARRAY
▸ [END OF IF]
▸ Step 6: EXIT By [Link],AP,Chandigarh Engineering College
8
 Program to perform Linear Search
#include<stdio.h>
#include<conio.h>
void main()
{
int a[11],b,c;
clrscr();
printf("Enter an array ");
for(b=0;b<11;b++)
{
scanf("%d",&a[b]);
}
printf("\nWhich value you want to search");
scanf("%d",&c);
for(b=0;b<11;b++)
{
if(a[b]==c)
{
printf("\nLocation of that value is %d",b+1);
break;
}
}
if(b==11)
printf("\nValue not found in array");
getch();
} 9
Binary Search
 Search an ordered array of integers for a value and return its index if the value
is found. Otherwise, return -1.

A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7]

1 2 3 5 7 10 14 17

 Binary search skips over parts of the array if the search value cannot possibly
be there.
By [Link],AP,Chandigarh Engineering College
10
6
11
12
 Binary Search Algorithm
▸ Step 1: [INITIALIZE] SET BEG = lower_bound
▸ END = upper_bound, POS = - 1
▸ Step 2: Repeat Steps 3 and 4 while BEG <= END
▸ Step 3: SET MID = (BEG + END)/2
▸ Step 4: IF A[MID] = VAL SET POS = MID PRINT POS Go to Step 6
▸ ELSE IF A[MID] > VAL
▸ SET END = MID - 1
▸ ELSE
▸ SET BEG = MID + 1
▸ [END OF IF]
▸ [END OF LOOP]
▸ Step 5: IF POS = -1
▸ PRINT “VALUE IS NOT PRESENT IN THE ARRAY”
▸ [END OF IF] Step 6: EXIT By [Link],AP,Chandigarh Engineering College
13
Binary Search
➢ Binary search is based on the “divide-and-conquer”
strategy which works as follows:
➢ Start by looking at the middle element of the array
➢ 1. If the value it holds is lower than the search element, eliminate
the first half of the array from further consideration.
➢ 2. If the value it holds is higher than the search element, eliminate
the second half of the array from further consideration.
➢ Repeat this process until the element is found, or until the
entire array has been eliminated.
By [Link],AP,Chandigarh Engineering College
14
 Example: binary search
A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7]
 14 ? 1 2 3 5 7 10 14 17
first mid last
A[4] A[5] A[6] A[7]
7 10 14 17
first mid last
A[6] A[7]
In this case,
(data[middle] == value)
return middle; 14 17
f mid last
By [Link],AP,Chandigarh Engineering College
15
 Example: binary search
A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7]
▸ 8?
1 2 3 5 7 10 14 17
first mid last
7 10 14 17
A[4] A[5] A[6] A[7]
first mid last
In this case, (first == last)
return -1;
7
A[4] f m l
16
 Example: binary search
 4? A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7]

1 2 3 5 7 10 14 17
first mid last
A[0] A[1] A[2]

1 2 3
first mid last
A[2]
In this case, (first ==
last)
return -1; 3
fml

By [Link],AP,Chandigarh Engineering College 17