Binary Search and Its Application on Arduino

Binary search is an efficient search algorithm that is particularly useful for finding elements in a sorted array. In comparison to linear search, which goes through each element one by one, binary search dramatically reduces the number of comparisons by dividing the search interval in half repeatedly. This is especially helpful for applications on resource-constrained microcontrollers like the Arduino.

In this tutorial, we’ll cover:

What is Binary Search?

Binary search works on a sorted array by repeatedly dividing the search interval in half. If the target value is less than the value in the middle of the interval, the search continues on the left half; otherwise, it continues on the right half. This division continues until the target is found or the interval is empty.

Binary Search Characteristics:

• Time Complexity: $O(\log n)$, which is much faster than a linear search’s $O(n)$.
• Condition: Works only on sorted arrays.

Implementing Binary Search on Arduino

To illustrate binary search, let’s start with a basic example on Arduino. Suppose we have a sorted array and we want to check if a given value exists within it.

Example Code

Let’s create a sorted array and a binary search function that returns the index of the target element or -1 if it’s not found.

int sortedArray[] = {2, 5, 7, 12, 15, 18, 21, 24, 27, 30};
int arraySize = sizeof(sortedArray) / sizeof(sortedArray[0]);

// Binary search function
int binarySearch(int array[], int size, int target) {
    int left = 0;
    int right = size - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;

        // Check if target is at mid
        if (array[mid] == target) {
            return mid;
        }
        
        // If target is greater, ignore left half
        if (array[mid] < target) {
            left = mid + 1;
        }
        // If target is smaller, ignore right half
        else {
            right = mid - 1;
        }
    }
    // Target is not present in array
    return -1;
}

void setup() {
    Serial.begin(9600);

    int target = 15; // Change this to test different values
    int result = binarySearch(sortedArray, arraySize, target);
    
    if (result != -1) {
        Serial.print("Element found at index: ");
        Serial.println(result);
    } else {
        Serial.println("Element not found.");
    }
}

void loop() {
    // No need to do anything here
}

In this example:

• We define a sorted array sortedArray.
• binarySearch() function takes in the array, its size, and the target value.
• If the target is found, it returns the index; otherwise, it returns -1.

Upload the code to your Arduino, open the Serial Monitor, and check the output. You should see the index of the target if it exists.

Using Binary Search to Map Values on Arduino

Now that we understand the basics of binary search, let’s look at a practical use case: mapping analog sensor readings to specific ranges or categories.

Suppose we have an analog sensor that provides varying readings from 0 to 1023, and we want to map these readings to certain ranges to make decisions. Binary search can quickly locate which range an analog reading belongs to, allowing the Arduino to respond based on this range.

Example: Mapping Sensor Readings to Predefined Ranges

Let’s say we have ranges defined as follows:

• Low: 0 to 200
• Medium: 201 to 600
• High: 601 to 800
• Very High: 801 to 1023

Using binary search, we can quickly find which range a reading falls into.

Code Example for Mapping with Binary Search

// Define range boundaries
int boundaries[] = {200, 600, 800, 1023};
String categories[] = {"Low", "Medium", "High", "Very High"};
int numCategories = sizeof(boundaries) / sizeof(boundaries[0]);

// Function to find the range index
int findRange(int value) {
    int left = 0;
    int right = numCategories - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;

        // If the value is less than or equal to the boundary
        if (value <= boundaries[mid]) { if (mid == 0 || value > boundaries[mid - 1]) {
                return mid;
            }
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1; // If value is out of range
}

void setup() {
    Serial.begin(9600);
}

void loop() {
    int sensorValue = analogRead(A0); // Read sensor value from analog pin A0
    int rangeIndex = findRange(sensorValue);

    if (rangeIndex != -1) {
        Serial.print("Sensor Value: ");
        Serial.print(sensorValue);
        Serial.print(" - Category: ");
        Serial.println(categories[rangeIndex]);
    } else {
        Serial.println("Value out of defined ranges.");
    }
    
    delay(1000); // Delay for readability in Serial Monitor
}

1. Range Boundaries: We define an array boundaries where each element represents the upper boundary of a range.
2. Category Array: categories holds labels for each range.
3. findRange Function: We use a modified binary search to quickly find which range the sensorValue belongs to. It checks if sensorValue is less than or equal to the midpoint boundary and returns the corresponding category.

When you run this code, the Arduino reads an analog value from A0 every second, determines the category it falls into, and displays it on the Serial Monitor.

Conclusion

Binary search is a powerful algorithm for quickly locating data in sorted arrays, and it’s especially useful in embedded systems where performance is key. In Arduino applications, binary search can be used effectively to categorize analog readings or even to manage larger datasets within the constraints of limited processing power. This approach allows us to make decisions based on data ranges efficiently and reliably.

Happy coding!