Binary Search is an efficient method for finding a specific value in a sorted array. This algorithm has a time complexity of O(log n) because it repeatedly divides the array in half to find the target value. In this lecture, we will cover the basic concepts of binary search, implementation methods, and practical exercises using this technique.
Basic Principle of Binary Search
Binary search operates according to the following procedure:
- Check the central element of the array.
- Compare the central element with the target value:
- If the target value is less than the central element, search in the left half of the array.
- If the target value is greater than the central element, search in the right half of the array.
- If the target value is equal to the central element, the search is complete.
This process is repeated until the target value is found.
Problem: Finding a Specific Value in a Sorted Array
Given an integer array arr
and an integer target
, write a program that returns the index of target
. If target
is not found, it should return -1
.
Input Format
- The first line contains the size of the array
n
. (1 ≤ n ≤ 105) - The second line contains the sorted array
arr
in ascending order. - The third line contains the number
target
to be found.
Output Format
Print the index of the target. (An integer between 0 and n-1)
Example
Input:
5
1 3 5 7 9
5
Output:
2
Solution Process
Step 1: Understanding the Problem
First, it is important to accurately understand the problem. Since we need to quickly find a specific element in a sorted array, we should use binary search.
Step 2: Implementing the Binary Search Algorithm
Let’s implement the binary search algorithm in C++.
#include <iostream>
#include <vector>
using namespace std;
int binarySearch(const vector<int> &arr, int target) {
int left = 0;
int right = arr.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid; // Found the target.
} else if (arr[mid] < target) {
left = mid + 1; // Move to the right half.
} else {
right = mid - 1; // Move to the left half.
}
}
return -1; // Target not found.
}
int main() {
int n;
cout << "Enter the size of the array: ";
cin >> n;
vector<int> arr(n);
cout << "Enter the elements of the array: ";
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
int target;
cout << "Enter the number you want to find: ";
cin >> target;
int result = binarySearch(arr, target);
if (result != -1) {
cout << "Index of the target: " << result << endl;
} else {
cout << "Target not found." << endl;
}
return 0;
}
Step 3: Code Explanation
– The binarySearch
function takes an integer vector and a target value as input and returns the index of the target value.
– left
and right
represent the start and end indices of the search interval.
– The while
loop runs while left
is less than or equal to right
.
– In each iteration, the central index mid
is computed, and the central element is compared with the target value to determine the next search interval.
Step 4: Testing and Verification
After writing the code, it is essential to run it against various test cases to ensure it returns the correct results. Consider the following tests:
- When the target value exists in the array
- When the target value does not exist in the array
- When the array size is 1
- When there are duplicate elements
Conclusion
Binary search is a very useful algorithm, especially as it exhibits excellent performance in terms of speed when working with sorted arrays. In this lecture, we understood the basic principles of binary search and implemented actual code. Mastering binary search will greatly help in solving many other algorithm problems.
In the next lecture, we will cover variations of binary search and various applications. I encourage you to enhance your algorithm skills through continuous learning!