ROLE PLAY
Subject: C Programming for Problem Solving
FACULTY INCHARGE: SANDEEP SIR
DESCRIPTION:
Binary search is a process of finding an element in the list of ‘n’ elements and are in sorted order.it works on the principle of finding the middle position,compare the key element with the middle element,if it matches then search is successful otherwise the key element may be present on the left or right side of the array by separating the middle position and repeat the procedure until you get a single element then conclude key element is found or not
Algorithm:
Step1:Start
Step2:Read the number of elements
Read the array elements
Read the key elements to be searched
Step3:Assign low=0
High=n-1
Mid=low+high/2
Step4:Check if(key==a[mid])
Assign flag=1
Break statement
Check if(key>a[mid])
Low=mid+1
else
high=mid-1
Step5: Check if(flag==1)
Display search successful and the position of the element
else
Display search unsuccessful
Step6: Stop
LOGIC:
Low=0;
high=n-1;
while(low<=high)
{
Mid=low+high/2;
If(key==a[mid])
{
Flag=1;
Break;
}
If(key>a[mid])
Low=mid+1;
Else
High=mid-1;
}
Example:
Enter the number of elements
9
Enter the 9 elements in ascending order
3 7 13 22 35 42 50 58 66
Enter the key element to be searched
22
Search successful and element found at the position 3
Explanation:
First low and high are assigned to 0th and 8th position.
Low=0
High=8
First iteration:
Mid=4
Key!= a[mid]
high =4 by high=mid-1
Second iteration:
Mid=1
Key!=a[mid]
Low=2 by low=mid+1
Third iteration:
Mid=2
Key!=a[mid]
Low=3 by low=mid+1
Fourth iteration:
Mid=3
Key= a[mid]
Search successful element found position at 3
