1.Binary Search Basics
Binary search is an efficient algorithm for finding a specific value in a sorted array. The basic idea is to repeatedly divide the search interval in half.
Algorithm Steps:
Start with the entire sorted array.
Calculate the middle index of the array.
Compare the element at the middle index with the target value.
If the middle element is equal to the target, the search is successful.
If the middle element is greater than the target, then the target must be in the lower half of the array. So, the search continues in the lower half.
If the middle element is less than the target, then the target must be in the upper half of the array. So, the search continues in the upper half.
Repeat these steps until the target is found or the search interval is empty.
Example:
Consider a sorted array arr = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20] and the target value is 10.
First, the middle index is (0 + 9)/2 = 4 (integer division). The element at index 4 is 10, which is the target value, so the search is successful.
Application on Arduino
Data Storage and Retrieval:
On an Arduino, you might have a sorted array of sensor calibration values. For example, if you have a temperature sensor and you have calibrated it at different known temperature points. Let's say you have an array of calibrated voltage - temperature pairs sorted by voltage. When you read a voltage from the sensor, you can use binary search to quickly find the corresponding temperature.
Code Example:
Here is a simple code example in C/C++ (which is used on Arduino) to perform a binary search on an array.
cpp
// Binary search function
int binarySearch(int arr[], int l, int r, int x) {
while (l <= r) {
int mid = l + (r - l) / 2;
// Check if x is present at mid
if (arr[mid] == x)
return mid;
// If x greater, ignore left half
else if (arr[mid] < x)
l = mid + 1;
// If x is smaller, ignore right half
else
r = mid - 1;
}
// If we reach here, then element was not present
return -1;
}
// Example usage
void setup() {
Serial.begin(9600);
int arr[] = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
int n = sizeof(arr)/sizeof(arr[0]);
int x = 10;
int result = binarySearch(arr, 0, n - 1, x);
if (result == -1)
Serial.println("Element not found");
else
Serial.println("Element found at index: " + String(result));
}
void loop() {}
In this example, the binarySearch function takes an array arr, the left index l, the right index r, and the target value x. The function returns the index of the target value if found, or -1 if not found. In the setup function, an array is defined, and the binary search is performed for a target value x. The result is then printed to the serial monitor.
Menu Navigation:
If you have a menu system on an Arduino with a sorted list of options (e.g., different modes of operation like "Mode 1", "Mode 2", "Mode 3", etc., sorted alphabetically or numerically), binary search can be used to quickly navigate to a specific option. The user enters a number or a keyword, and the binary search algorithm can find the corresponding menu option in an efficient manner.
Resource Management:
In a more complex Arduino project with limited memory, you might have a sorted list of available memory blocks. Binary search can be used to quickly find a memory block of a suitable size for a new task or data storage, reducing the search time compared to a linear search.
Top comments (0)