A topic on a ternary, binary search problem

Binary search operates by identifying the center item in a set of data and matching it with the target item. If it finds a match, it returns the index of the matched item. If the targeted item has a lesser value than the center item, the search continues within the left sub-array. In contrast, if the targeted item has a greater value than the center item, the search continues within the right sub-array. This approach continues until the sub-array size becomes zero.

Despite the initial creation of the binary search algorithm in 1946, the coding for this method surfaced as a significant challenge with the first error-free version appearing in 1962. A bug was even discovered in Java's own Arrays.binarySearch() method in 2006.

int binarySearch(int arr[], int target) {
    int left = 0, right = arr.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target)
            return mid;
        if (arr[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return -1;  // return -1 if target is not found
}

In a binary search implementation, we should first create two pointers the left pointer and the right pointer. Their purpose is to keep track of the beginning and the end of the area we're searching within the array.

Next, the algorithm introduces a loop that doesn't stop until the left pointer surpasses the right one. Inside the loop, we find the middle point using the two pointers and then discuss the three potential outcomes.

1. When the middle point equals the target, its index gets returned.

2. If it's less than the target, we increase the left pointer.

3. In the other case, we decrease the right pointer.

We repeat these steps until we find our target or when the loop condition becomes false. If the latter occurs, we return -1.

Ternary search

Ternary search is a divide-and-conquer algorithm, similar to binary search, that is used to find a specific element in an array. However, unlike binary search which divides the array into two parts, ternary search divides the array into three parts to determine which section contains the key (the element being searched for). This division into three parts is achieved by calculating two midpoints, mid1 and mid2. Initially, the left (l) and right (r) boundaries are set to 0 and n-1, respectively, where n is the length of the array.

Here's what the Java implementation of the ternary search algorithm looks like.

int ternarySearch(int arr[], int target) {
    int left = 0, right = arr.length - 1;
    while (right >= left) {
        int mid1 = left + (right - left) / 3;
        int mid2 = right - (right - left) / 3;
        if (arr[mid1] == target)
            return mid1;
        if (arr[mid2] == target)
            return mid2;
        if (target < arr[mid1])
            right = mid1 - 1;
        else if (target > arr[mid2])
            left = mid2 + 1;
        else {
            left = mid1 + 1;
            right = mid2 - 1;
        }
    }
    return -1;  // return -1 if target is not found
}

As you can see, it's quite similar to the binary search implementation.

Binary search in action

To better comprehend these two methods' uses, let's examine some coding challenges like the "Search in Rotated Sorted Array" problem from LeetCode. The problem is as follows:

You are given a sorted integer array nums (with distinct values) in ascending order, that has been twisted at an unknown point. For instance, [0, 1, 2, 4, 5, 6, 7] could become [4, 5, 6, 7, 0, 1, 2] after a rotation. You also have a target integer.

Your task is to ascertain if target is in the array. If it is, return the index; else, return -1.

public class SearchInRotatedSortedArray {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] == target) {
                // Target found, return its index
                return mid;
            }

            if (nums[mid] >= nums[left]) {
                // Left half is sorted

                // Check if the target falls within the sorted left half
                if (target >= nums[left] && target < nums[mid]) {
                    // Adjust the search range to the left half
                    right = mid - 1;
                } else {
                    // Adjust the search range to the right half
                    left = mid + 1;
                }
            } else {
                // Right half is sorted

                // Check if the target falls within the sorted right half
                if (target > nums[mid] && target <= nums[right]) {
                    // Adjust the search range to the right half
                    left = mid + 1;
                } else {
                    // Adjust the search range to the left half
                    right = mid - 1;
                }
            }
        }

        // Target not found in the array
        return -1;
    }
}

The code you see above is the Java solution to this problem. But how exactly does it work?

• Two pointers, left and right are set to map the start and end of the search range in the rotated array.

• We then enter a while loop that continues until left is less than or equal to right. The loop terminates when the search range gets exhausted.

• In each round, we calculate the middle index mid using (left + right) / 2. That's where we verify the element against the target.

• Initially, we test if nums[mid] matches the target. If it does, we return the index mid implying we found the target.

• After that, we determine if the left or right half is ordered. If nums[mid] >= nums[left], it indicates the left half is sorted; otherwise, the right half is ordered.

• When the left half is sorted, we test if the target lies within the sorted span. If it does, we change the search range to concentrate on the left half by setting right = mid - 1. If it doesn't, we set left = mid + 1 to focus on the right half.

• If the right half is sorted, we follow the same approach but adjust the search span accordingly.

• We repeat these procedures until left is higher than right. If the target isn't found during this process, -1 is returned indicating that the target doesn't exist in the array.

The binary search approach efficiently shortens the search range each round, ensuing a time efficiency of O(log n) for this algorithm.

Ternary search for maximum

As we discussed earlier, the ternary search is typically utilized to find the maximum or lowest value of a unimodal function within a defined span. The problem statement and solution using ternary search are as follows:

You have a continuous, unimodal function f(x) that exclusively rises on one side of the peak and exclusively descends on the other. Your goal is to find the x value where f(x) attains its maximum value within the given range [left, right].

To solve this problem using ternary search, follow these steps:

1. Designate left and right to single out the range within which you want to find the maximum value of f(x).

2. Use a loop to continue until the range [left, right] is small enough (e.g., when right - left is smaller than a certain tolerance).

3. Compute two intermediary points, m1 and m2. These points divide the range [left, right] into three equal parts. You can calculate these points as follows:

   • m1 = left + (right - left) / 3

   • m2 = right - (right - left) / 3

4. Determine the values of f(m1) and f(m2).

5. Compare f(m1) and f(m2):

   • If f(m1) < f(m2), it means that the maximum value of f(x) lies to the right of m1. So, update left = m1.

   • If f(m1) > f(m2), it means that the maximum value of f(x) lies to the left of m2. So, update right = m2.

6. Repeat steps 3 to 5 until the range [left, right] is small enough.

7. Return the value of x where f(x) reaches its maximum value.

Here's a Java illustration of the above approach:

public class TernarySearchMaximization {
    // Define the function f(x) here
    private double f(double x) {
        // Replace this with the actual function
        return -(x * x); // Example: maximizing a negative quadratic function
    }

    public double findMax(double left, double right, double tolerance) {
        while (right - left > tolerance) {
            double m1 = left + (right - left) / 3.0;
            double m2 = right - (right - left) / 3.0;
            double f1 = f(m1);
            double f2 = f(m2);

            if (f1 < f2) {
                left = m1;
            } else {
                right = m2;
            }
        }

        // Return the x value that corresponds to the maximum value of f(x)
        return (left + right) / 2.0;
    }
}

In this example, we maximize a simple negative quadratic function -(x * x) using ternary search. You can replace the f(x) function with your own unimodal function to find the maximum value within a specified range [left, right].

The overall time complexity of the ternary search algorithm is $O(log((right-left) / tolerance))$. This represents the number of iterations required to approximate the maximum value of the unimodal function within the specified range [left, right] with the specified tolerance level. The tolerance level, often denoted as tolerance in the context of optimization algorithms like ternary search, is a user-defined parameter that specifies how close the approximation needs to be to the true maximum or minimum value of the function being optimized. A smaller tolerance level indicates a higher level of precision, but it may require more iterations to achieve. Conversely, a larger tolerance level allows for a less precise approximation but may converge faster.

Binary vs. Ternary search

The binary search algorithm is used quite often by programmers because of its algorithmic time complexity. The worst-case runtime of this algorithm is $O(log_2N)$, where N is the number of elements in the array. This is the case because after each iteration we reduce the given array to half its size.

Although ternary search is similar to binary search, it offers a slight improvement in time complexity. The algorithm executes in N steps, where the search range is the $size = 3^N$. Inversely, the number of steps required to find an element is the logarithm of the collection size. Hence, the runtime complexity is $O(log_3 N)$.

However, in practice, when comparing the two methods with the Big O notation $O(log_2N) = O(log_3N)$ because the numbers 2 and 3 act simply as constants, and as we know in Big O notation comparisons constants are ignored making both algorithms $O(logN)$. Thus binary search is usually more efficient, because it makes one comparison per level of search, whereas ternary search makes two. This extra comparison adds more processing time, negating the advantage of fewer levels in the search tree.

Conclusion

Binary and ternary searches are highly efficient algorithms that are widely used in computer science to solve search problems. They both adopt a divide-and-conquer strategy, splitting the data into smaller parts and conducting search within these sections, significantly decreasing search time.

Due to its simplicity and effectiveness, binary search is often the preferred method. Regardless of its apparent simplicity, correct implementation requires careful attention, as seen from the history of bugs found in various implementations, including Java's Arrays.binarySearch() method.

On the other hand, ternary search splits the data into three parts. While it theoretically offers a slight improvement in time complexity, practical performance may not be as efficient as binary search due to the additional comparisons it entails.

Here are some key points to remember:

• Binary search operates by repeatedly dividing the search space in half, making it an incredibly efficient algorithm with a time complexity of $O(log_2N)$.

• Ternary search, which divides the search space into thirds, theoretically improves the time complexity to $O(log_3N)$, but the extra comparisons might decrease its efficiency in practice.

• Careful attention is critical for the correct implementation of these strategies, to avoid common pitfalls and errors.

• The choice between binary and ternary searches depends on your problem's specific requirements and constraints.