A binary search is an efficient algorithm used to search for a specific value within a sorted collection of data. In order to eliminate the fraction of the data that cannot contain the required value, the search space is cut in half periodically.

The binary search algorithm follows these steps:

1. Start with the entire sorted collection of data.
2. Compare the target value with the middle element of the collection.
3. The search is complete if the target value is equal to the central element.
4. If the target value is less than the central element, the search continues on the lower half of the collection.
5. If the target value exceeds the central element, the search continues on the upper half of the collection.
6. Repeat steps 2-5 until the target value is found or the search space is empty.

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.

Here binary search flowchart

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.

Binary Search in c

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.

The 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

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

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

Red is mid

As A[mid] = 55

Print “Search is Successful”

Result: Given element 55 is found at the 5th  position

Given that the size of the input data, n, determines the temporal complexity of an algorithm, the binary search algorithm is particularly significant. As a result, the search time increases logarithmically as the size of the data set increases. The temporal complexity of a straightforward linear search, in contrast, is O(n), and the search time scales linearly with the quantity of the data.

Binary search is very useful for huge data sets when short search times are essential due to its efficiency. It is frequently used in a variety of applications, including looking for a certain value in a binary search tree, searching for an element in a sorted array, and using an index to find something in a database.

Binary search lowers the number of comparisons needed to discover the target value by halving the search space at each stage. When working with huge datasets or conducting several searches, this efficiency is very beneficial. It enables quicker information retrieval and enhances overall performance across a range of computer science and software engineering jobs.

Binary Search FAQs

Related posts

Last updated on Sunday - June 4th, 2023