Solution: :
Solution: Step1:
first last 0 7
Solution: :
Solution: Step1 (continued…)
mid=(first+last)/2
first mid last 0 7 3 20 <26
Solution: :
Solution: Step2: last=mid-1
first mid last 0 2 1 20 > 13
Solution: :
Solution: Step3: first=mid+1
mid=(first+last)/2
mid first last 0 2 1 20 > 17
Solution: :
Solution: Step4: first=mid+1
mid last first
first <=last (false)
Target=mid (false)
Search Unsuccessful !!! 0 2 1
Different cases in Binary search :
Different cases in Binary search Best case: In this case the search item is at mid(first mid).so the iteration is 1.
Average case: In this case the search item is somewhere on the either side of the mid(first mid).
Worst case: In this case the search item is at the first or last position in the list.
Or
It is not present in the list
Efficiency of Binary Search :
Efficiency of Binary Search Binary search locates an item repeatedly dividing the list in half.
Therefore reduces the iteration.
The loop used is binary search is a logarithmic loop.
Hence,
The efficiency of binary search is O(log n)
Comparison of binary and sequential search :
Comparison of binary and sequential search