Binary Search: If data to be searched in sorted array, In such cases we use a vastly superior method to find a match named Binary Search which uses the divide and conquer approach. To employ this method, test the middle element. If it is larger than key(element to be searched), test the middle element of the first half; otherwise test the middle element of lower half. Repeat this procedure until a match is found or there is no more elements to test.
For Example, to find number 4 in Array :
1 2 3 4 5 6 7 8 9
A binary search first tests the middle element, which is 5. Since 5 is greater than 4, the search continues in first half, or
1 2 3 4 5
The middle element is now 3. This is less than 4, so first half is discarded, and search continues with
4 5
This time the match is found.
No. of Comparisons (Worst Case) = log2 n
No. of Comparisons (Best Case) = 0
No. of Comparisons for Average Case are somewhat lower as compared to Worst Case.
For Example, to find number 4 in Array :
1 2 3 4 5 6 7 8 9
A binary search first tests the middle element, which is 5. Since 5 is greater than 4, the search continues in first half, or
1 2 3 4 5
The middle element is now 3. This is less than 4, so first half is discarded, and search continues with
4 5
This time the match is found.
No. of Comparisons (Worst Case) = log2 n
No. of Comparisons (Best Case) = 0
No. of Comparisons for Average Case are somewhat lower as compared to Worst Case.
by anil nain 9416077273
No comments:
Post a Comment