## Binary Search

### Q) Explain the binary search with an algorithm.

• Binary search is an efficient search as compared to a linear search. it is used to search elements from a sorted array.
• In the search middle element of an array is compared with the item, if they are equal then a search is successful.
• Otherwise, if item > middle element then perform searching in the upper half or if item<middle element then perform searching in the lower half.

### Working Binary Search

• Initially set beg = 1 and end = size of the array, then find the middle of an array using mid= (beg+end)/2.
• Compare array[mid] with the item to be searched, if they are equal the search is successful and the process is stopped.
• When the value of item >  array[mid] then proceed to search in the upper half using beg = mid + 1. Otherwise, when the value of item < array [mid] then proceeds to search in the lower half using end = mid – 1.
• The same steps are repeated in the respective half until the element is found or beg <= end.

### Algorithm: Binary_Serach[Data[], lb, ub, item, loc]

• This is the algorithm for linear search
• Data[]- Array of an element,
• lb- lower bound,
• ub – upper bound,
• beg -beginning position,
• end – end position,
• mid – middle position,
• item – element to be searched,
• loc – location.
step 1: start
step 2 : [initialize variable]
Set beg=lb, end=ub,loc=0
step 3 :  Repeat steps4, 5 and 6 until beg <= end and data[mid] != item
step 4 :  [find middle]
mid=(beg+end)/2
step 5 : [compare data[mid] and item]
if data [mid] == item the
set loc=mid
End if
step 6 : [jump in respective half]
if item >data[mid]then
beg = mid + 1
else
end = mid-1
step 7 : if loc == 0 then
else
Print “item is found at loc”
step 8 : Stop

### Example Binary Search

Consider the following example containing 8sorted array elements.
1 2 3 4 5 6 7 8
11 22 33 44 55 66 77 88
Element to be searched is: 55
set
beg = 1 and
end = 8
Pass 1
Find mid
mid = (ben+end)/2
mid = (1+8)/2
mid = 4
compare A[mid] with 55
1 2 3 4 5 6 7 8
11 22 33 44 55 66 77 88
Red is mid
As A[mid] != 55 &
55 > A[mid] Proceed searching in the Upper half
Set beg = mid + 1
beg = 4 + 1
beg = 5

Pass 2
Find mid
mid = (beg+end)/2
mid = (5+8)/2
mid = 6
compare A[mid] with55
1 2 3 4 5 6 7 8
11 22 33 5 55 66 77 88
Red is mid
As A[mid] != 55 &
55 < A[mid] Proceed searching in the lower half
Set end = mid-1
end = 6 – 1
end = 5
Pass 3
Find mid
mid = (beg+end)/2
mid = (5+5)/2
mid = 5
compareA[mid] with 55
1 2 3 4 5 6 7 8
11 22 33 44 55 66 77 88
Red is mid
As A[mid] = 55
Print “Search is Successful”
Result: Given element 55 is found at 5th  position

Last updated on Sunday - May 21st, 2023

.