- The binary search algorithm is a fast and efficient searching technique used to locate a specific element in a sorted array. It follows a divide-and-conquer approach, repeatedly dividing the search interval in half. Here’s how the binary search algorithm works:
Key Features Of The Binary Search Algorithm Include
- Sorted Data Requirement: Binary search requires the data to be sorted beforehand, enabling the algorithm to discard half of the search space at each step.
- Efficient Time Complexity: It has a time complexity of O(log n), where n is the number of elements in the array. This makes it highly efficient for large datasets, as the search time increases logarithmically with the size of the dataset.
- Divide-and-Conquer Strategy: The algorithm divides the search interval in half and selects the half that could potentially contain the target value, continuing this process until the target value is found or the interval is empty.
- Midpoint Comparison: Binary search compares the target value with the middle element of the array and recursively narrows down the search space based on the comparison result.
Algorithm
Binary_Search(a, lower_bound, upper_bound, val)
// 'a' is the given array, 'lower_bound' is the index
of the first array element, 'upper_bound' is the
index of the last array element, 'val' is the
value to search
Step 1: set beg = lower_bound, end = upper_bound,
pos = - 1
Step 2: repeat steps 3 and 4 while beg <=end
Step 3: set mid = (beg + end)/2
Step 4: if a[mid] = val
set pos = mid
print pos
go to step 6
else if a[mid] > val
set end = mid - 1
else
set beg = mid + 1
[end of if]
[end of loop]
Step 5: if pos = -1
print "value is not present in the array"
[end of if]
Step 6: exit
Working Of Binary search
The binary search algorithm efficiently finds the position of a target value within a sorted array. Here is how the binary search algorithm works:
- Step 1: Begin with the entire sorted array.
- Step 2: Identify the middle element of the array.
- Step 3: Compare the middle element with the target value.
- Step 4: If the middle element is the target value, the search is successful, and the position is returned.
- Step 5: If the target value is less than the middle element, continue the search on the lower half of the array. If the target value is greater, continue the search on the upper half.
- Step 6: Repeat steps 2-5 until the target value is found, or the search interval is empty.
Binary Search Complexity
Time Complexity:
| Case | Time Complexity |
|---|---|
| Best Case | O(1) |
| Average Case | O(logn) |
| Worst Case | O(logn) |
- Best Case Complexity – In Binary search, best case occurs when the element to search is found in first comparison, i.e., when the first middle element itself is the element to be searched. The best-case time complexity of Binary search is O(1).
- Average Case Complexity – The average case time complexity of Binary search is O(logn).
- Worst Case Complexity – In Binary search, the worst case occurs, when we have to keep reducing the search space till it has only one element. The worst-case time complexity of Binary search is O(logn).
