Explain binary search algorithm in detail.
SOLUTION....
Binary Search Algorithm – Detailed Explanation
Searching is one of the most common operations in computer science. Whenever we deal with data, one frequent task is to check whether a specific element is present in a collection or not. The binary search algorithm is one of the most efficient methods to perform this task, but it works only when the data is sorted (either in ascending or descending order).
What is Binary Search?
Binary Search is a divide and conquer algorithm that finds the position of a target element within a sorted array or list. Instead of checking every element one by one (like in linear search), binary search repeatedly divides the search space into half until the target element is found or the search space becomes empty.
This makes binary search much faster than linear search, especially for large datasets.
Working Principle
Let’s assume we have a sorted array. The binary search algorithm follows these steps:
Initialize pointers
Start with two pointers:
low→ beginning index of the array.high→ ending index of the array.
Find the middle element
Calculate the middle index:
(In actual code, it’s often written as
mid = low + (high - low) // 2to avoid overflow.)
Compare the middle element with the target
If the middle element equals the target, the search is successful.
If the target is smaller than the middle element, update the search space to the left half by setting
high = mid - 1.If the target is larger than the middle element, update the search space to the right half by setting
low = mid + 1.
Repeat the process
Continue steps 2 and 3 untillowis greater thanhigh. If no match is found, the element is not present in the array.
Example
Suppose we have a sorted array:
arr = [5, 10, 15, 20, 25, 30, 35]
We want to search for 25.
Step 1:
low = 0,high = 6mid = (0 + 6) / 2 = 3arr[3] = 20Since
25 > 20, search moves to the right half →low = 4.
Step 2:
low = 4,high = 6mid = (4 + 6) / 2 = 5arr[5] = 30Since
25 < 30, search moves to the left half →high = 4.
Step 3:
low = 4,high = 4mid = (4 + 4) / 2 = 4arr[4] = 25, which is the target.
✅ Element 25 found at index 4.