Exploring the Modified Binary Search Algorithm

Binary search is a classic algorithm used to efficiently search for an element in a sorted array. However, there’s a modified version of binary search that comes in handy when we’re dealing with specific situations. In this article, we’ll delve into the modified binary search algorithm, its key decisions, and when to use it.

The Original Binary Search Algorithm

To understand the modified version, let’s briefly recap the original binary search algorithm:

The above algorithm uses left <= right as the loop termination condition. If the target is found, the index is returned. Otherwise, left and right pointers are adjusted based on comparisons with arr[mid].

Original BS algorithm is best to find exact match of the element in sorted array but many times it is not useful. Sometimes we do not only want to find matching element in sorted array but we also want its first occurrence within the array. For example, you are trying to find index of first number in array which is < 100. In this case, there can be many potential answers as in below example, but we want to find the first occurrence of element which is less than 100. arr = [1000, 10, 20, 50, 70, 80, 91, 92, 93]. In this example, If we search for number which is less than 100. Our first mid which is 70 will be the answer which is incorrect answer. We want to still continue to search for more better answer by remembering our current answer which is 70. Here, the modified binary search kicks in. We will use of left pointer to point to the answer and keep looking for answers. In the end, we will return left to indicate the answer.

Introducing the Modified Binary Search

The modified binary search algorithm uses a slight variation in the loop termination condition and handling of the pointers. Here’s the template code:

When to Use Modified Binary Search

The modified binary search algorithm is particularly useful in scenarios where you’re looking for:

• The leftmost occurrence of an element in a sorted array, especially when dealing with duplicates.
• The insertion point for an element in a sorted array.
• The lower bound of a value, the smallest element not less than the given value.

Choose the modified binary search when your goal aligns with these situations. For general search needs, the original binary search algorithm with left <= right remains effective.

Key Decisions Explained

1. Loop Termination Condition (left < right):

• In the modified binary search, we use left < right as the loop termination condition instead of left <= right. This decision impacts how the search range is narrowed down.
• When left becomes equal to or greater than right, we've narrowed the search to a single element or no elements.

2. Updating high (right = mid):

• The critical difference lies in updating the high pointer. Instead of right = mid - 1, we set right = mid.
• This decision ensures that the element at index mid is still included in the search range, allowing us to find the leftmost occurrence.

3. Returning left at the End:

• The return value is determined by checking if the element at arr[left] equals the target.
• If found, the leftmost index of the target is returned. Otherwise, -1 is returned to indicate that the target wasn't found.

Most Importantly,

The main purpose of the modified binary search algorithm is to find the leftmost occurrence of an element in a sorted array.

• If we find a potential candidate for the leftmost occurrence at index mid, we want to search in the left half of the array to see if there's an earlier occurrence. So, we need to include the element at index mid in the next search range.
• If we set high = mid + (or) - 1, we would be excluding the element at index mid from the next search range, which could result in skipping the leftmost occurrence.

By setting high = mid, we ensure that the element at index mid is included in the next search range if it's a potential candidate for the leftmost occurrence. This allows the algorithm to continue searching for an earlier occurrence in the left half of the array.

In conclusion, understanding and utilizing the modified binary search algorithm gives you an additional tool to tackle specific search challenges efficiently. It demonstrates the beauty of algorithms — how small changes can make a big impact on problem-solving.