Algorithms and Flowchart Binary Search

Ishwaranand / 3 years
3 min read

Post Views: 44

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.

binary search stl, binary search python, binary search java, binary search in c binary search geeksforgeeks, binary search program in c, binary search recursive, binary search time complexity, binary search example step by step, linear search, binary search javascript, binary search c++ stl, binary search - leetcode, binary search in c using recursion, binary search c#, time complexity of binary search tree, binary search vs linear search, interpolation search simulation, binary search stl, the binary search algorithm quizlet, binary search javascript khan academy, binary search competitive programming, binary search program in c++, data structures searching problems,

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 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

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 at 5th position

Last updated on Sunday - May 21st, 2023