Modified Binary search
- User
Modified Binary search
- 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
- Why “Modified”?
- Prerequisite: Always a Sorted Array
- 1. First Occurrence of Target
- 2. Last Occurrence of Target
- 3. Lower Bound (First ≥ Target)
- 4. Upper Bound (Last ≤ Target)
- 5. Search in Rotated Sorted Array
- 6. Find Minimum in Rotated Array
- 7. Peak in a Bitonic Array
- Time & Space Complexity
- Common Pitfalls
- Downloadable Code File
1. Why “Modified”?
Classic binary search finds any index of
targetin 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/highwhenarr[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
isuch thatarr[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
isuch thatarr[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
isuch thatarr[i] ≥ target.
If all elements < target, returnarr.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
isuch thatarr[i] > target.
If all elements ≤ target, returnarr.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
targetor-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
- Integer overflow when computing
mid = (low+high)/2.
Always usemid = low + (high – low)/2. - Infinite loop in lower/upper bound if you use
low <= highinstead oflow < high. - Off‐by‐one when deciding whether to move
loworhigh. 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 ModifiedBinarySearchFeel free to tweak, test edge cases, and integrate into your own projects.
Happy coding! 🚀
- User
list out questions on leetcode based on binarySearch algo. Keep order from easy to medium to hard
- 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
-
704. Binary Search
Classic: find a target in a sorted array.
https://leetcode.com/problems/binary-search/ -
35. Search Insert Position
Find the index where a target should be inserted into a sorted array.
https://leetcode.com/problems/search-insert-position/ -
278. First Bad Version
Binary‐search on version range to find the first bad one.
https://leetcode.com/problems/first-bad-version/ -
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/ -
69. Sqrt(x)
Compute the integer square root using binary search.
https://leetcode.com/problems/sqrtx/
🔷 Medium
-
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/ -
33. Search in Rotated Sorted Array
Binary‐search in a rotated (pivoted) sorted array.
https://leetcode.com/problems/search-in-rotated-sorted-array/ -
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/ -
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/ -
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
-
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/ -
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/ -
875. Koko Eating Bananas
Binary‐search the eating‐speed (answer space) to finish within H hours.
https://leetcode.com/problems/koko-eating-bananas/ -
410. Split Array Largest Sum
Binary‐search the maximum subarray sum threshold over m splits.
https://leetcode.com/problems/split-array-largest-sum/ -
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! 🚀
-
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.