Algorithms and Flowchart Binary Search

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, it item > middle element then perform searching in the upper half or if item<middle element then perform searching in the lower half. 

Image Source ~ Crafted With ©Ishwaranand - 2020 ~ Image by ©Ishwaranand

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 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 search,
• 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] == itme 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

                 Print "item is not found"

            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 ar 5th  position.