## 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, if 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 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