Binary Search in Java: Theory and Applications

In-depth exploration of binary search algorithm in Java, including iterative and recursive implementations, and its applications in problem-solving.

⬅ Previous Next ➡

Binary Search Variations in Competitive Programming (Java)

Binary search is a powerful and efficient algorithm for finding a specific element within a sorted array. Its time complexity of O(log n) makes it ideal for large datasets. However, the basic binary search can be extended to solve a variety of related problems. This document explores common and useful variations of binary search frequently encountered in competitive programming, illustrated with Java solutions.

Understanding the Core Binary Search Algorithm

Before diving into variations, let's recap the standard binary search algorithm:

Start with a sorted array.
Initialize left to the starting index (0) and right to the ending index (array.length - 1).
While left <= right:
- Calculate the middle index: mid = left + (right - left) / 2; (This prevents potential overflow).
- If array[mid] == target, return mid.
- If array[mid] < target, the target must be in the right half, so left = mid + 1.
- If array[mid] > target, the target must be in the left half, so right = mid - 1.
If the target is not found, return -1.

 // Basic Binary Search
            public static int binarySearch(int[] arr, int target) {
                int left = 0;
                int right = arr.length - 1;

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

                    if (arr[mid] == target) {
                        return mid;
                    } else if (arr[mid] < target) {
                        left = mid + 1;
                    } else {
                        right = mid - 1;
                    }
                }
                return -1; // Target not found
            }

Variations of Binary Search

1. Finding the First Occurrence of an Element

If the target element appears multiple times in the sorted array, this variation finds the index of its first appearance.

Algorithm:

Perform a standard binary search.
If the target is found at index mid, don't immediately return.
Instead, update right = mid - 1 and continue the search in the left half. This is because the first occurrence might be to the left of mid.
Keep track of the leftmost index where the target was found.

 public static int findFirstOccurrence(int[] arr, int target) {
                        int left = 0;
                        int right = arr.length - 1;
                        int firstOccurrence = -1;

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

                            if (arr[mid] == target) {
                                firstOccurrence = mid;
                                right = mid - 1; // Continue searching in the left half
                            } else if (arr[mid] < target) {
                                left = mid + 1;
                            } else {
                                right = mid - 1;
                            }
                        }

                        return firstOccurrence;
                    }

Example:

 int[] arr = {2, 5, 5, 5, 6, 6, 8, 9};
                    int target = 5;
                    int first = findFirstOccurrence(arr, target); // first will be 1
                    System.out.println("First occurrence of " + target + ": " + first);

2. Finding the Last Occurrence of an Element

Similar to finding the first occurrence, this variation identifies the index of the last appearance of the target element.

Algorithm:

Perform a standard binary search.
If the target is found at index mid, don't immediately return.
Instead, update left = mid + 1 and continue the search in the right half. This is because the last occurrence might be to the right of mid.
Keep track of the rightmost index where the target was found.

 public static int findLastOccurrence(int[] arr, int target) {
                        int left = 0;
                        int right = arr.length - 1;
                        int lastOccurrence = -1;

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

                            if (arr[mid] == target) {
                                lastOccurrence = mid;
                                left = mid + 1; // Continue searching in the right half
                            } else if (arr[mid] < target) {
                                left = mid + 1;
                            } else {
                                right = mid - 1;
                            }
                        }

                        return lastOccurrence;
                    }

Example:

 int[] arr = {2, 5, 5, 5, 6, 6, 8, 9};
                    int target = 5;
                    int last = findLastOccurrence(arr, target); // last will be 3
                    System.out.println("Last occurrence of " + target + ": " + last);

3. Finding the Smallest Element Greater Than or Equal to the Target (Ceiling)

This variation finds the smallest element in the array that is greater than or equal to the given target. If all elements are smaller than the target, it should return the length of the array (or -1 if that's the chosen sentinel value).

Algorithm:

Perform a standard binary search.
If arr[mid] >= target, it's a potential candidate for the ceiling. Update right = mid - 1 to search for an even smaller element that still satisfies the condition. Also, store the current arr[mid] as the best ceiling seen so far.
If arr[mid] < target, update left = mid + 1 to search in the right half.

 public static int findCeiling(int[] arr, int target) {
                        int left = 0;
                        int right = arr.length - 1;
                        int ceiling = -1; //Or arr.length

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

                            if (arr[mid] >= target) {
                                ceiling = arr[mid];
                                right = mid - 1;
                            } else {
                                left = mid + 1;
                            }
                        }

                        return ceiling;
                    }

                  public static int findCeilingIndex(int[] arr, int target) {
                        int left = 0;
                        int right = arr.length - 1;
                        int ceilingIndex = -1; // Or arr.length

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

                            if (arr[mid] >= target) {
                                ceilingIndex = mid;
                                right = mid - 1;
                            } else {
                                left = mid + 1;
                            }
                        }

                        return ceilingIndex;
                    }

Example:

 int[] arr = {2, 3, 5, 6, 8, 11};
                    int target = 4;
                    int ceiling = findCeiling(arr, target); // ceiling will be 5
                    System.out.println("Ceiling of " + target + ": " + ceiling);

Example finding the index:

 int[] arr = {2, 3, 5, 6, 8, 11};
                    int target = 4;
                    int ceilingIndex = findCeilingIndex(arr, target); // ceilingIndex will be 2
                    System.out.println("Ceiling index of " + target + ": " + ceilingIndex);

4. Finding the Largest Element Smaller Than or Equal to the Target (Floor)

This variation finds the largest element in the array that is smaller than or equal to the given target. If all elements are larger than the target, return -1.

Algorithm:

Perform a standard binary search.
If arr[mid] <= target, it's a potential candidate for the floor. Update left = mid + 1 to search for an even larger element that still satisfies the condition. Also, store the current arr[mid] as the best floor seen so far.
If arr[mid] > target, update right = mid - 1 to search in the left half.

 public static int findFloor(int[] arr, int target) {
                        int left = 0;
                        int right = arr.length - 1;
                        int floor = -1;

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

                            if (arr[mid] <= target) {
                                floor = arr[mid];
                                left = mid + 1;
                            } else {
                                right = mid - 1;
                            }
                        }

                        return floor;
                    }

                    public static int findFloorIndex(int[] arr, int target) {
                        int left = 0;
                        int right = arr.length - 1;
                        int floorIndex = -1;

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

                            if (arr[mid] <= target) {
                                floorIndex = mid;
                                left = mid + 1;
                            } else {
                                right = mid - 1;
                            }
                        }

                        return floorIndex;
                    }

Example:

 int[] arr = {2, 3, 5, 6, 8, 11};
                    int target = 7;
                    int floor = findFloor(arr, target); // floor will be 6
                    System.out.println("Floor of " + target + ": " + floor);

Example Finding index:

 int[] arr = {2, 3, 5, 6, 8, 11};
                    int target = 7;
                    int floorIndex = findFloorIndex(arr, target); // floor will be 3
                    System.out.println("Floor index of " + target + ": " + floorIndex);

5. Searching in a Rotated Sorted Array

A rotated sorted array is an array that was initially sorted but then rotated by some number of positions. For example, [4, 5, 6, 7, 0, 1, 2] is a rotated version of [0, 1, 2, 4, 5, 6, 7]. The challenge is to find a target element in this rotated array efficiently (ideally in O(log n) time).

Algorithm:

Find the Pivot: The pivot is the index of the smallest element in the array. It's the point where the array is rotated. Use binary search to find this pivot. In the rotated array, the element before the pivot is greater than the element at the pivot.
Determine the Search Range: Once you have the pivot, you can determine which part of the array (before or after the pivot) the target might be in.
Apply Binary Search: Apply standard binary search in the appropriate range.

 public static int searchRotatedArray(int[] nums, int target) {
                        int n = nums.length;
                        int left = 0;
                        int right = n - 1;

                        // Find the pivot
                        while (left < right) {
                            int mid = left + (right - left) / 2;
                            if (nums[mid] > nums[right]) {
                                left = mid + 1;
                            } else {
                                right = mid;
                            }
                        }

                        int pivot = left;  // 'left' is the index of the minimum element

                        // Determine search range
                        left = 0;
                        right = n - 1;

                        if (target >= nums[pivot] && target <= nums[right]) {
                            left = pivot;
                        } else {
                            right = pivot - 1;
                        }


                        // Standard Binary Search in the determined range
                        while (left <= right) {
                            int mid = left + (right - left) / 2;
                            if (nums[mid] == target) {
                                return mid;
                            } else if (nums[mid] < target) {
                                left = mid + 1;
                            } else {
                                right = mid - 1;
                            }
                        }

                        return -1; // Target not found
                    }

Example:

 int[] nums = {4, 5, 6, 7, 0, 1, 2};
                    int target = 0;
                    int index = searchRotatedArray(nums, target); // index will be 4
                    System.out.println("Index of " + target + ": " + index);

6. Finding the Peak Element in an Unimodal Array

A unimodal array is an array that strictly increases to a peak and then strictly decreases. The goal is to find the index of this peak element. Binary Search is highly effective here.

Algorithm:

Use Binary Search to iterate through the array.
At each middle element mid:
- If arr[mid] > arr[mid + 1], it means the peak is either at mid or somewhere to the left of mid. So, update right = mid.
- Otherwise, the peak is to the right of mid. Update left = mid + 1.
The loop continues until left == right, which will be the index of the peak.

 public static int findPeakElement(int[] arr) {
                        int left = 0;
                        int right = arr.length - 1;

                        while (left < right) {
                            int mid = left + (right - left) / 2;
                            if (arr[mid] > arr[mid + 1]) {
                                right = mid;
                            } else {
                                left = mid + 1;
                            }
                        }

                        return left; // 'left' will be the index of the peak
                    }

Example:

 int[] arr = {1, 3, 8, 12, 4, 2};
                    int peakIndex = findPeakElement(arr); // peakIndex will be 3
                    System.out.println("Peak element index: " + peakIndex);

Tips for Competitive Programming

Understand the problem constraints: Pay close attention to the size of the input array, the range of values, and the required time complexity. This will help you determine if binary search is an appropriate approach.
Edge cases: Always consider edge cases such as empty arrays, arrays with a single element, target values outside the array range, and duplicate elements.
Off-by-one errors: Binary search is prone to off-by-one errors. Double-check your conditions (left <= right vs. left < right) and your updates to left and right (mid + 1 vs. mid).
Practice, practice, practice: The best way to master binary search variations is to practice solving a variety of problems. Online judge platforms like Codeforces, LeetCode, and HackerRank have many problems that can be solved using binary search.

By understanding these variations and practicing consistently, you can effectively utilize binary search to solve a wide range of problems in competitive programming.

⬅ Previous Next ➡