Skip to content
TheChatArchiveThe Chat Archive
Mistralmistral-medium-2505· Mistral AIHugging Face LMArena Human Preference 140K

Modified Binary search

From a Chatbot Arena battleThe same person sent this prompt to two anonymous models at once. Compare it with o4-mini-2025-04-16’s answer.
  1. User

    Modified Binary search

  2. Mistral Assistant

    Modified Binary Search Algorithms in Java

    Binary search is a powerful algorithm that can be adapted to solve various problems beyond simple element lookup. Here are several important modified versions of binary search that are commonly used in programming interviews and real-world applications.

    1. Finding First and Last Occurrence of an Element

    When dealing with sorted arrays that contain duplicates, you often need to find the first or last occurrence of a target value.

    Finding First Occurrence

    public int findFirstOccurrence(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int firstOccurrence = -1;
    
        while (left <= right) {
            int mid = left + (right - left) / 2;
    
            if (nums[mid] == target) {
                firstOccurrence = mid;  // Record the position
                right = mid - 1;       // Continue searching in left half
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    
        return firstOccurrence;
    }
    

    Finding Last Occurrence

    public int findLastOccurrence(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int lastOccurrence = -1;
    
        while (left <= right) {
            int mid = left + (right - left) / 2;
    
            if (nums[mid] == target) {
                lastOccurrence = mid;   // Record the position
                left = mid + 1;        // Continue searching in right half
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    
        return lastOccurrence;
    }
    

    2. Finding the Ceiling and Floor of a Number

    The ceiling of a number is the smallest element in the array that is greater than or equal to the target. The floor is the largest element that is less than or equal to the target.

    Finding Ceiling

    public int findCeiling(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int ceiling = -1;
    
        while (left <= right) {
            int mid = left + (right - left) / 2;
    
            if (nums[mid] == target) {
                return nums[mid];
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                ceiling = nums[mid];
                right = mid - 1;
            }
        }
    
        return ceiling;
    }
    

    Finding Floor

    public int findFloor(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int floor = -1;
    
        while (left <= right) {
            int mid = left + (right - left) / 2;
    
            if (nums[mid] == target) {
                return nums[mid];
            } else if (nums[mid] < target) {
                floor = nums[mid];
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    
        return floor;
    }
    

    3. Finding the Number of Occurrences of an Element

    public int countOccurrences(int[] nums, int target) {
        int first = findFirstOccurrence(nums, target);
        if (first == -1) {
            return 0;  // Target not found
        }
        int last = findLastOccurrence(nums, target);
        return last - first + 1;
    }
    

    4. Finding the Peak Element

    A peak element is an element that is greater than its neighbors. For corner elements, we only need to consider one neighbor.

    public int findPeakElement(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
    
        while (left < right) {
            int mid = left + (right - left) / 2;
    
            if (nums[mid] < nums[mid + 1]) {
                left = mid + 1;  // Peak is in the right half
            } else {
                right = mid;     // Peak is in the left half (including mid)
            }
        }
    
        return left;  // or right, since they'll be equal
    }
    

    5. Search in a Rotated Sorted Array

    This is a classic problem where a sorted array is rotated at some pivot point. We need to find the index of a target value.

    public int searchInRotatedArray(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) {
                return mid;
            }
    
            // Check if the left half is sorted
            if (nums[left] <= nums[mid]) {
                // Target is in the left half
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            // Otherwise, the right half must be sorted
            else {
                // Target is in the right half
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
    
        return -1;
    }
    

    6. Finding the Minimum in a Rotated Sorted Array

    public int findMinInRotatedArray(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
    
        while (left < right) {
            int mid = left + (right - left) / 2;
    
            // If the right half is sorted, the minimum is there
            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else {
                right = mid;  // The minimum could be mid or in the left half
            }
        }
    
        return nums[left];
    }
    

    7. Finding the Square Root of a Number

    public int findSquareRoot(int x) {
        if (x == 0 || x == 1) {
            return x;
        }
    
        int left = 1;
        int right = x;
        int result = 0;
    
        while (left <= right) {
            int mid = left + (right - left) / 2;
    
            if (mid * mid == x) {
                return mid;
            } else if (mid * mid < x) {
                left = mid + 1;
                result = mid;  // Store the potential result
            } else {
                right = mid - 1;
            }
        }
    
        return result;
    }
    

    8. Finding the Kth Missing Positive Number

    public int findKthMissingPositive(int[] arr, int k) {
        int left = 0;
        int right = arr.length - 1;
    
        while (left <= right) {
            int mid = left + (right - left) / 2;
    
            // Calculate how many numbers are missing before arr[mid]
            int missing = arr[mid] - (mid + 1);
    
            if (missing < k) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    
        // The kth missing number is arr[right] + (k - missing)
        return arr[right] + (k - (arr[right] - (right + 1)));
    }
    

    9. Finding the Kth Smallest Element in Two Sorted Arrays

    public int findKthSmallest(int[] nums1, int[] nums2, int k) {
        // Ensure nums1 is the smaller array to minimize operations
        if (nums1.length > nums2.length) {
            return findKthSmallest(nums2, nums1, k);
        }
    
        int m = nums1.length;
        int n = nums2.length;
    
        int left = 0;
        int right = m;
    
        while (left <= right) {
            int partition1 = left + (right - left) / 2;
            int partition2 = k - partition1;
    
            // Handle cases where partition2 is out of bounds
            if (partition2 < 0) {
                right = partition1 - 1;
                continue;
            }
            if (partition2 > n) {
                left = partition1 + 1;
                continue;
            }
    
            int maxLeft1 = (partition1 == 0) ? Integer.MIN_VALUE : nums1[partition1 - 1];
            int minRight1 = (partition1 == m) ? Integer.MAX_VALUE : nums1[partition1];
    
            int maxLeft2 = (partition2 == 0) ? Integer.MIN_VALUE : nums2[partition2 - 1];
            int minRight2 = (partition2 == n) ? Integer.MAX_VALUE : nums2[partition2];
    
            if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
                return Math.max(maxLeft1, maxLeft2);
            } else if (maxLeft1 > minRight2) {
                right = partition1 - 1;
            } else {
                left = partition1 + 1;
            }
        }
    
        return -1; // Should not reach here if inputs are correct
    }
    

    10. Finding the Kth Largest Element in an Array

    public int findKthLargest(int[] nums, int k) {
        int left = 0;
        int right = nums.length - 1;
        k = nums.length - k; // Convert to kth smallest
    
        while (left <= right) {
            int pivotIndex = partition(nums, left, right);
    
            if (pivotIndex == k) {
                return nums[pivotIndex];
            } else if (pivotIndex < k) {
                left = pivotIndex + 1;
            } else {
                right = pivotIndex - 1;
            }
        }
    
        return -1; // Should not reach here if inputs are correct
    }
    
    private int partition(int[] nums, int left, int right) {
        int pivot = nums[right];
        int i = left;
    
        for (int j = left; j < right; j++) {
            if (nums[j] <= pivot) {
                swap(nums, i, j);
                i++;
            }
        }
    
        swap(nums, i, right);
        return i;
    }
    
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    

    These modified binary search algorithms demonstrate the versatility of the binary search technique. By understanding these variations, you can tackle a wide range of problems that involve searching or analyzing sorted data structures.

  3. User

    list out questions on leetcode based on binarySearch algo. Keep order from easy to medium to hard

  4. Mistral Assistant

    Here's a categorized list of LeetCode problems based on binary search, ordered from easy to medium to hard difficulty levels:

    Easy Level (Fundamentals of Binary Search)

    1. Binary Search (LeetCode 704)

      • Classic implementation of binary search on a sorted array
    2. Search Insert Position (LeetCode 35)

      • Find the position where a target should be inserted in a sorted array
    3. First Bad Version (LeetCode 278)

      • Find the first bad version in a sequence of versions
    4. Sqrt(x) (LeetCode 69)

      • Calculate the integer square root of a non-negative integer
    5. Two Sum II - Input array is sorted (LeetCode 167)

      • Find two numbers that add up to a target using binary search

    Medium Level (Variations and Applications)

    1. Find Peak Element (LeetCode 162)

      • Find any peak element in an array
    2. Find Minimum in Rotated Sorted Array (LeetCode 153)

      • Find the minimum element in a rotated sorted array
    3. Search in Rotated Sorted Array (LeetCode 33)

      • Search for a target in a rotated sorted array
    4. Find First and Last Position of Element in Sorted Array (LeetCode 34)

      • Find the starting and ending position of a target value
    5. Find K Closest Elements (LeetCode 658)

      • Find k closest elements to a given value
    6. Find the Duplicate Number (LeetCode 287)

      • Find the duplicate number in an array using binary search
    7. Search a 2D Matrix (LeetCode 74)

      • Search for a value in a 2D matrix with sorted rows and columns
    8. Search a 2D Matrix II (LeetCode 240)

      • Search for a value in a 2D matrix with sorted rows and columns (more complex)
    9. Find Kth Smallest Pair Distance (LeetCode 719)

      • Find the kth smallest distance between pairs of elements
    10. Find Right Interval (LeetCode 436)

      • Find the right interval for each interval in an array

    Hard Level (Advanced Applications)

    1. Median of Two Sorted Arrays (LeetCode 4)

      • Find the median of two sorted arrays using binary search
    2. Split Array Largest Sum (LeetCode 410)

      • Split an array into m subarrays with the largest sum minimized
    3. Find in Mountain Array (LeetCode 1095)

      • Find a target in a mountain-shaped array (bitonic sequence)
    4. Kth Smallest Element in a Sorted Matrix (LeetCode 378)

      • Find the kth smallest element in a sorted matrix
    5. Maximum Number of Removable Characters (LeetCode 1898)

      • Find the maximum number of removable characters to maintain a subsequence
    6. Kth Missing Positive Number (LeetCode 1539)

      • Find the kth missing positive number in an array
    7. Find the Smallest Divisor Given a Threshold (LeetCode 1283)

      • Find the smallest divisor such that the sum of divisions is less than a threshold
    8. Capacity To Ship Packages Within D Days (LeetCode 1011)

      • Find the minimum capacity to ship packages within D days
    9. Minimum Number of Days to Make m Bouquets (LeetCode 1482)

      • Find the minimum number of days to make m bouquets with k adjacent flowers
    10. Kth Smallest Number in Multiplication Table (LeetCode 668)

      • Find the kth smallest number in a multiplication table

    This progression from easy to hard problems will help you build a strong foundation in binary search and then apply it to more complex scenarios. Each problem introduces new variations and applications of the binary search technique.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.