Skip to content
TheChatArchiveThe Chat Archive
o4-mini-2025-04-16· OpenAIHugging 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 Mistralmistral-medium-2505’s answer.
  1. User

    Modified Binary search

  2. Assistant

    Here’s a concise yet thorough guide to “Modified Binary Search” in Java. It covers the most common variations of binary search that you’ll encounter in interview problems or real-world coding tasks. You can save this as a Markdown (.md) or convert it to PDF/Word. At the end is a downloadable Java file with all examples.


    Modified Binary Search in Java

    Table of Contents

    1. Why “Modified”?
    2. Prerequisite: Always a Sorted Array
    3. 1. First Occurrence of Target
    4. 2. Last Occurrence of Target
    5. 3. Lower Bound (First ≥ Target)
    6. 4. Upper Bound (Last ≤ Target)
    7. 5. Search in Rotated Sorted Array
    8. 6. Find Minimum in Rotated Array
    9. 7. Peak in a Bitonic Array
    10. Time & Space Complexity
    11. Common Pitfalls
    12. Downloadable Code File

    1. Why “Modified”?

    Classic binary search finds any index of target in a sorted array. “Modified” versions tweak the loop conditions or pointer movements to find:

    • the first or last occurrence when duplicates exist
    • the proper insertion point (lower/upper bound)
    • special targets in rotated arrays or bitonic (mountain) arrays

    These are all O(log n) and differ only in how you adjust low/high when arr[mid] == target.


    2. Prerequisite: Always a Sorted Array

    Every variant below assumes you’re working on a sorted (ascending) array. If it’s not sorted, results are undefined.

    int[] arr = {1,2,2,2,3,4,5};
    

    3. First Occurrence of Target

    Find the leftmost index i such that arr[i] == target.
    If not found, return -1.

    public static int firstOccurrence(int[] arr, int target) {
        int low = 0, high = arr.length - 1, result = -1;
        while (low <= high) {
            int mid = low + (high - low)/2;
            if (arr[mid] == target) {
                result = mid;
                high = mid - 1; // continue left
            } else if (arr[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return result;
    }
    

    4. Last Occurrence of Target

    Find the rightmost index i such that arr[i] == target.
    If not found, return -1.

    public static int lastOccurrence(int[] arr, int target) {
        int low = 0, high = arr.length - 1, result = -1;
        while (low <= high) {
            int mid = low + (high - low)/2;
            if (arr[mid] == target) {
                result = mid;
                low = mid + 1; // continue right
            } else if (arr[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return result;
    }
    

    5. Lower Bound (First ≥ Target)

    Return the smallest index i such that arr[i] ≥ target.
    If all elements < target, return arr.length (insertion at end).

    public static int lowerBound(int[] arr, int target) {
        int low = 0, high = arr.length;
        while (low < high) {
            int mid = low + (high - low)/2;
            if (arr[mid] < target) {
                low = mid + 1;
            } else {
                high = mid; // mid might be answer
            }
        }
        return low;
    }
    

    6. Upper Bound (First > Target)

    Return the smallest index i such that arr[i] > target.
    If all elements ≤ target, return arr.length.

    public static int upperBound(int[] arr, int target) {
        int low = 0, high = arr.length;
        while (low < high) {
            int mid = low + (high - low)/2;
            if (arr[mid] <= target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }
    

    7. Search in Rotated Sorted Array

    Given a rotated sorted array (no duplicates), find index of target or -1:

    // e.g. arr = [  4,5,6,7,0,1,2 ], target=0 → index=4
    public static int searchRotated(int[] arr, int target) {
        int low = 0, high = arr.length - 1;
        while (low <= high) {
            int mid = low + (high - low)/2;
            if (arr[mid] == target) return mid;
    
            // left half is sorted?
            if (arr[low] <= arr[mid]) {
                if (arr[low] <= target && target < arr[mid])
                    high = mid - 1;
                else
                    low = mid + 1;
            }
            // right half must be sorted
            else {
                if (arr[mid] < target && target <= arr[high])
                    low = mid + 1;
                else
                    high = mid - 1;
            }
        }
        return -1;
    }
    

    8. Find Minimum in Rotated Array

    Return the minimum element in a rotated sorted array (no duplicates):

    public static int findMinInRotated(int[] arr) {
        int low = 0, high = arr.length - 1;
        while (low < high) {
            int mid = low + (high - low)/2;
            if (arr[mid] > arr[high]) {
                // min is in right half
                low = mid + 1;
            } else {
                // min is in left half including mid
                high = mid;
            }
        }
        return arr[low];
    }
    

    9. Peak in a Bitonic (Mountain) Array

    A bitonic array first increases then decreases. Find the peak index:

    public static int findBitonicPeak(int[] arr) {
        int low = 0, high = arr.length - 1;
        while (low < high) {
            int mid = low + (high - low)/2;
            if (arr[mid] < arr[mid+1]) {
                // ascending, peak to the right
                low = mid + 1;
            } else {
                // descending, peak is mid or left
                high = mid;
            }
        }
        return low; // or high
    }
    

    10. Time & Space Complexity

    • Time: O(log n) for every variant—each step halves the search space.
    • Space: O(1) for iterative methods.

    11. Common Pitfalls

    1. Integer overflow when computing mid = (low+high)/2.
      Always use mid = low + (high – low)/2.
    2. Infinite loop in lower/upper bound if you use low <= high instead of low < high.
    3. Off‐by‐one when deciding whether to move low or high. Draw a number line!

    12. Downloadable Code File

    You can copy this into ModifiedBinarySearch.java:

    // ModifiedBinarySearch.java
    
    public class ModifiedBinarySearch {
        // 1. First Occurrence
        public static int firstOccurrence(int[] arr, int target) {
            int low = 0, high = arr.length - 1, result = -1;
            while (low <= high) {
                int mid = low + (high - low)/2;
                if (arr[mid] == target) {
                    result = mid;
                    high = mid - 1;
                } else if (arr[mid] < target) {
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }
            return result;
        }
    
        // 2. Last Occurrence
        public static int lastOccurrence(int[] arr, int target) {
            int low = 0, high = arr.length - 1, result = -1;
            while (low <= high) {
                int mid = low + (high - low)/2;
                if (arr[mid] == target) {
                    result = mid;
                    low = mid + 1;
                } else if (arr[mid] < target) {
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }
            return result;
        }
    
        // 3. Lower Bound (first >= target)
        public static int lowerBound(int[] arr, int target) {
            int low = 0, high = arr.length;
            while (low < high) {
                int mid = low + (high - low)/2;
                if (arr[mid] < target) {
                    low = mid + 1;
                } else {
                    high = mid;
                }
            }
            return low;
        }
    
        // 4. Upper Bound (first > target)
        public static int upperBound(int[] arr, int target) {
            int low = 0, high = arr.length;
            while (low < high) {
                int mid = low + (high - low)/2;
                if (arr[mid] <= target) {
                    low = mid + 1;
                } else {
                    high = mid;
                }
            }
            return low;
        }
    
        // 5. Search in Rotated Sorted Array
        public static int searchRotated(int[] arr, int target) {
            int low = 0, high = arr.length - 1;
            while (low <= high) {
                int mid = low + (high - low)/2;
                if (arr[mid] == target) return mid;
                if (arr[low] <= arr[mid]) {
                    if (arr[low] <= target && target < arr[mid])
                        high = mid - 1;
                    else
                        low = mid + 1;
                } else {
                    if (arr[mid] < target && target <= arr[high])
                        low = mid + 1;
                    else
                        high = mid - 1;
                }
            }
            return -1;
        }
    
        // 6. Find Min in Rotated Array
        public static int findMinInRotated(int[] arr) {
            int low = 0, high = arr.length - 1;
            while (low < high) {
                int mid = low + (high - low)/2;
                if (arr[mid] > arr[high]) {
                    low = mid + 1;
                } else {
                    high = mid;
                }
            }
            return arr[low];
        }
    
        // 7. Find Peak in Bitonic Array
        public static int findBitonicPeak(int[] arr) {
            int low = 0, high = arr.length - 1;
            while (low < high) {
                int mid = low + (high - low)/2;
                if (arr[mid] < arr[mid+1]) {
                    low = mid + 1;
                } else {
                    high = mid;
                }
            }
            return low;
        }
    
        // Main to test them
        public static void main(String[] args) {
            int[] arr = {1,2,2,2,3,4,5};
            System.out.println("First of 2: " + firstOccurrence(arr,2)); // 1
            System.out.println("Last of 2: "  + lastOccurrence(arr,2));  // 3
            System.out.println("LB of 2: "    + lowerBound(arr,2));      // 1
            System.out.println("UB of 2: "    + upperBound(arr,2));      // 4
    
            int[] rot = {4,5,6,7,0,1,2};
            System.out.println("Search 0 in rotated: " + searchRotated(rot,0)); // 4
            System.out.println("Min in rotated: "      + findMinInRotated(rot)); // 0
    
            int[] bit = {1,3,8,12,4,2};
            System.out.println("Peak in bitonic: " + findBitonicPeak(bit)); // 3 (value 12)
        }
    }
    

    Compile & run:

    javac ModifiedBinarySearch.java
    java ModifiedBinarySearch
    

    Feel free to tweak, test edge cases, and integrate into your own projects.

    Happy coding! 🚀

  3. User

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

  4. Assistant

    Below is a curated list of LeetCode problems that all leverage the binary‐search idea—either to search a sorted array or to “binary‐search” an answer space. They’re grouped by difficulty (Easy → Medium → Hard). Each entry includes the problem number, title, a one‐line description, and a link.


    🟢 Easy

    1. 704. Binary Search
      Classic: find a target in a sorted array.
      https://leetcode.com/problems/binary-search/

    2. 35. Search Insert Position
      Find the index where a target should be inserted into a sorted array.
      https://leetcode.com/problems/search-insert-position/

    3. 278. First Bad Version
      Binary‐search on version range to find the first bad one.
      https://leetcode.com/problems/first-bad-version/

    4. 167. Two Sum II – Input Array Is Sorted
      Use two‐pointers (a form of binary idea) to find two numbers summing to target.
      https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/

    5. 69. Sqrt(x)
      Compute the integer square root using binary search.
      https://leetcode.com/problems/sqrtx/


    🔷 Medium

    1. 34. Find First and Last Position of Element in Sorted Array
      Two modified binary searches for the first and last occurrence.
      https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

    2. 33. Search in Rotated Sorted Array
      Binary‐search in a rotated (pivoted) sorted array.
      https://leetcode.com/problems/search-in-rotated-sorted-array/

    3. 153. Find Minimum in Rotated Sorted Array
      Locate the inflection point (minimum) in a rotated sorted array.
      https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/

    4. 74. Search a 2D Matrix
      Treat the 2D matrix as a flat sorted array and binary‐search.
      https://leetcode.com/problems/search-a-2d-matrix/

    5. 240. Search a 2D Matrix II
      Advanced 2D‐matrix search using a mix of binary search and pruning.
      https://leetcode.com/problems/search-a-2d-matrix-ii/


    🔴 Hard

    1. 4. Median of Two Sorted Arrays
      Find the median of two sorted arrays in O(log(m+n)) time.
      https://leetcode.com/problems/median-of-two-sorted-arrays/

    2. 378. Kth Smallest Element in a Sorted Matrix
      Binary‐search on value range plus counting ≤ mid in each row.
      https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/

    3. 875. Koko Eating Bananas
      Binary‐search the eating‐speed (answer space) to finish within H hours.
      https://leetcode.com/problems/koko-eating-bananas/

    4. 410. Split Array Largest Sum
      Binary‐search the maximum subarray sum threshold over m splits.
      https://leetcode.com/problems/split-array-largest-sum/

    5. 1011. Capacity To Ship Packages Within D Days
      Binary‐search the ship capacity needed to deliver within D days.
      https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/


    Feel free to tackle them in order: start with the basics, then move on to rotated/2D variants, and finally master “binary‐search on answers.” Good luck! 🚀

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