Introduction:
Searching is a common operation in computer science and programming.
Binary search is a popular searching algorithm that is used to find the position of an element in a sorted array.
In this blog, we will discuss binary search, its algorithm, implementation, and pros and cons.
Definition:
Binary search is a searching algorithm that works on a sorted array. It starts by comparing the middle element of the array with the target element.
If the middle element is the target element, the search is complete. If the middle element is greater than the target element, the search continues in the lower half of the array.
If the middle element is less than the target element, the search continues in the upper half of the array.
The process is repeated until the target element is found or the search space is exhausted.
Problem Statement:
Given a sorted array and a target element, find the position of the target element in the array.
arr = [5, 2, 8, 12, 1, 6]
Brute Force:
One way to solve this problem is to use a linear search algorithm.
It involves iterating through each element of the array until the target element is found.
This approach has a time complexity of O(n) which can be inefficient for large arrays.
When and why to use Binary Search:
Binary search is an efficient algorithm for searching a sorted array.
It has a time complexity of O(log n) which is much faster than linear search.
Binary search is useful when the array is large, and the target element is not at the beginning or end of the array.
It is commonly used in programming for tasks such as finding the index of a value in a sorted array, finding the minimum or maximum value in a sorted array, or checking if an element exists in a sorted array.
Algorithm:
1. Get the input sorted array and target element.
2. Set the start index to 0 and end index to the length of the array minus 1.
3. While the start index is less than or equal to the end index, do the following:
a. Calculate the middle index as the average of the start and end indices.
b. If the middle element is equal to the target element, return the middle index.
c. If the middle element is greater than the target element, set the end index to the middle index minus 1.
d. If the middle element is less than the target element, set the start index to the middle index plus 1.
4. If the target element is not found, return -1.
Solution:
Hands on solution:
Here is the C++ code for binary search:
using namespace std;
int binarySearch(int arr[], int n, int target) {
int start = 0, end = n - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] > target) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return -1;
}
int main() {
int arr[] = {1, 3, 5, 7, 9};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 5;
int result = binarySearch(arr, n, target);
if (result == -1) {
cout << "Element not found." << endl;
} else {
cout << "Element found at index " << result << "." << endl;
}
return 0;
}
Leet Code Solution:
public:
int search(vector<int>& nums, int target) {
int low = 0;
int high = nums.size()-1;
while(low <= high){
int mid = low + (high-low)/2;
if(nums[mid] == target){
return mid;
}
else if(nums[mid] < target){
low = mid+1;
}
else
high = mid-1;
}
return -1;
}
};
Pros and Cons:
Pros of Binary search:
1. Binary search is an efficient algorithm with a time complexity of O(log n).
2. It works well on large sorted arrays.
3. It can be used to find the index of a value in a sorted array, find the minimum or maximum value in a sorted array, or check if an element exists in a sorted array.
Cons of Binary search:
1. Binary search only works on sorted arrays.
2. It requires extra memory to store the indices of the start and end points of the search space.
3. If the array is not sorted, the algorithm will not work correctly.
Binary search is a powerful algorithm that can save time and effort when searching for elements in a sorted array. By understanding its algorithm and implementation, you can use it to efficiently solve a variety of programming problems.