📌Highlights: Hi Friends ! In this post I am going to explain the concept of Binary Search , How this will work, How to write Binary Search Algorithm, How to write the procedure of Binary Search in C.How to find their complexity and example.
Binary Search method is based on divide and conquer strategy. In Binary search first we find mid position element of array and point it to the (MID) index pointer. Now we compare searching element (S) to MID element. Such that
If MID position element is greater than (S) then we discard second part of array and continue binary search with first part from (LOW) to (MID-1).
If MID position is less than (S) then we discard first part of array and continue Binary Search with second part from (MID+1) to (HIGH).
We proceed above method until array has a single element.
Note: In the above method we assume array is already sorted in ascending order.
It is short story about Binary sort Let we understand in very simple way by the help of an example:
N = 8 // Number of elements in an array
LOW = 0 //First elements of array
HIGH = N-1 // Last element of array
MID = (LOW + HIGH) / 2
S = MID
Now check Condition
If (A[MID] == S )
For True
RETURN (MID)
For False
Again Check Condition
If A(MID) > S
For True
Consider first part i.e from [LOW ,MID+1] // Discard Second Part
Apply Same procedure in first part.
For False i.e A(MID) < S
Consider second part i.e from [MID + 1, HIGH] // Discard First Part
Apply Same procedure in second part.
Binary Search can perform by two methods:
1. Non Recursive Search.
2. Recursive Binary Search.
PROCEDURE FOR NON RECURSIVE BINARY SEARCH:
int BSearch ( int A[50], int N, int S)
{
int LOW , MID, HIGH;
LOW = 0;
HIGH = N-1;
WHILE (LOW <= HIGH)
{
MID = (LOW + HIGH ) /2;
IF (A[MID] == S)
{
RETURN (MID);
}
ELSE
{
IF (A[MID] > S)
{
HIGH = MID -1;
}
ELSE
{
LOW = MID +1;
}
}
}
RETURN (-1);
}
ALGORITHM FOR NON RECURSIVE BINARY SEARCH:
A is an array of N elements
STEP 1: LOW =0
STEP 2: HIGH = N-1
STEP 3: WHILE (LOW <= HIGH)
STEP 4: MID = (LOW + HIGH ) / 2
STEP 5: IF A[MID] == S
STEP 6: RETURN (MID)
STEP 7: ELSE
STEP 8: IF ( A[MID] >S)
STEP 9: HIGH = MID -1
STEP 10: ELSE
STEP 11: LOW = MID +1
STEP 12: END IF
STEP 13: END IF
STEP 14: END WHILE
STEP 15: RETURN (-1)
STEP 16: END
PROCEDURE FOR RECURSIVE BINARY SEARCH:
int BSearch ( int A[50], int LOW, int HIGH, int S)
{
int MID ;
IF (LOW <= HIGH)
{
MID = (LOW + HIGH ) /2;
IF (A[MID] == S)
{
RETURN (MID);
}
ELSE
{
IF (A[MID] > S)
{
BSearch ( A, LOW, MID -1, S); // Recursive call on first part of array
}
ELSE
{
BSearch ( A, MID + 1, HIGH, S);
}
}
}
RETURN (-1);
}
ALGORITHM FOR RECURSIVE BINARY SEARCH:
A is an array of N elements
STEP 1: IF (LOW <= HIGH)
STEP 2: MID = (LOW + HIGH ) / 2
STEP 3: IF A[MID] == S
STEP 4: RETURN (MID)
STEP 5: ELSE
STEP 6: IF ( A[MID] >S)
STEP 7: RECURSIVELY CALL BSearch
BSearch(A, LOW, MID -1 , S)
STEP 8: ELSE
STEP 9: RECURSIVELY CALL BSearch
BSearch(A, MID +1, HIGH , S)
STEP 10: END IF
STEP 11: END IF
STEP 12: RETURN (-1)
STEP 13: END
EXAMPLE:
Suppose Searching element (S) = 25
LOW=0
HIGH=7
First we find (MID)
MID = (0 + 7 ) / 2 = 3 // According to above formula.
Now check Condition
If (A[3] == 25 ) // False go to Else statement
For True
RETURN (MID)
For False
Again Check Condition
If A(3) > 25 // False go to Else statement i.e (17>25 false)
For True
Consider first part i.e from [LOW ,MID+1] // Discard Second Part
Apply Same procedure in first part.
For False i.e A(3) < 25 // i.e 17<25 true
Consider second part i.e from [3 + 1, 7] // Discard First Part
Apply Same procedure in second part. i.e form (4 to 7)
Elements are (19 ,25, 31, 80) such as:
Now check condition:
If( A[1]==25) // True i.e 25 =25
RETURN 25
EVALUATION OF BINARY SEARCH:
1. BEST CASE :
Best case for binary search occur when element is found in first attempt. In such case it needs just one comparison with complexity O(1).
2. WORST CASE:
Worst case for binary search occur when search element is not in array. In such case for an array of (n) element binary search need at most (log2n) comparison with complexity O(log2n).
ADVANTAGES AND DISADVANTAGES OF BINARY SEARCH AND SEQUENTIAL SEARCH:
ADVANTAGES OF SEQUENTIAL SEARCH:
1. Sequential search can be applicable in any type of storage structure.
2. Generally there are two type of storage structure.
i. Sequential structure storage device like : link list, tape device etc.
ii. It can perform on unsorted structure.
DISADVANTAGE OF BINARY SEARCH:
1. It can perform direct access storage device . like: Array.
2. It can applicable in only sorted elements.
ADVANTAGE OF BINARY SEARCH:
1. It is very fast method and take very less time.
📌Friends ! It is end of this post. It is all about binary search, I hope this post is helpful for you. We will meet on new post till continue reading.
No comments:
Post a Comment