arr = [2, 4, 6, 9, 11, 12, 14, 20, 36, 48];
This is sorted array and in ascending order
target to search → 36
Find the middle element
Check :
If target > middle → search in right
else → search in left
If target == middle → we found element.
Here, the space in which we are searching is getting divided into two spaces.
Time complexity:
Best Case : O(1)
Worst Case : O(logn)
Explanation : find the maximum number of comparisons
N/2k = 1
N = 2k log(N) = log(2k)
log(N) = klog2
k = logN/log2
k = log2N
public class Binary {
public static void main(String[] args) {
int[] arr = { -18, -16, 0, 5, 8, 9, 12, 50, 60, 88, 99 };
int target = 600;
int ans = binarySearch(arr, target);
System.out.println(ans);
}
// return the index
// return -1 if it does not exist
static int binarySearch(int[] arr, int target) {
int start = 0;
int end = arr.length - 1;
while (start <= end) {
// find the middle element
// int mid = (start + end)/2; meight be poosible that (start + end) exceeds
// range of integer in java
int mid = start + (end - start) / 2;
if (target < arr[mid]) {
end = mid - 1;
} else if (target > arr[mid]) {
start = mid + 1;
} else {
return mid;
}
}
return -1;
}
}
Order agnostic Binary Search
Let's say if we don't know that the array is sorted in ascending or descending order
arr = [90, 75, 18, 12, 6, 4, 3, 1] target = 75
Here, target > middle → search in left
Here, start > end → descending order
when start > end → ascending order
public class Binary {
public static void main(String[] args) {
// int[] arr = {-18, -12, -4, 0, 2, 3, 4, 15, 16, 18, 22, 45, 89};
int[] arr = { 99, 80, 75, 22, 11, 10, 5, 2, -3 };
int target = 22;
int ans = orderAgnosticBS(arr, target);
System.out.println(ans);
}
static int orderAgnosticBS(int[] arr, int target) {
int start = 0;
int end = arr.length - 1;
// find whether the array is sorted in ascending or descending
boolean isAsc = arr[start] < arr[end];
while (start <= end) {
int mid = start + (end - start) / 2;
if (arr[mid] == target)
return mid;
if (isAsc) {
if (target < arr[mid])
end = mid - 1;
else
start = mid + 1;
} else {
if (target > arr[mid])
end = mid - 1;
else
start = mid + 1;
}
}
return -1;
}
}
Questions
Q→ When do we apply binary search?
If if you have to do something with sorted array
First try binary search on it
Q→ Find Ceiling of a number
In a given sorted array
ceiling = smallest element which is greater or equal to target element.
public class Binary {
public static void main(String[] args) {
int[] arr = { -18, -12, -4, 0, 2, 3, 4, 15, 16, 18, 22, 45, 89 };
// int[] arr = { 99, 80, 75, 22, 11, 10, 5, 2, -3 };
int target = 17;
int ans = ceiling(arr, target);
System.out.println(ans);
}
// return the index of smallest no >= target
static int ceiling(int[] arr, int target) {
// but what if the target is greater then
// the greatest number is the array
if(target > arr[arr.length-1])
return -1;
int start = 0;
int end = arr.length - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (target < arr[mid])
end = mid - 1;
else if (target > arr[mid])
start = mid + 1;
else
return mid;
}
return start;
}
}
Q→ Find floor of a number
In a given sorted array
floor = greatest element which is smaller or equal to target element.
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] ans = {-1, -1};
// check for first occurrence if target first
int start = search(nums, target, true);
int end = search(nums, target, false);
ans[0]=start;
ans[1]=end;
return ans;
}
// this function just returns the index value of target
int search(int [] nums, int target, boolean findStartIndex){
int ans = -1;
int start = 0;
int end = nums.length - 1;
while (start <= end) {
// find the middle element
// int mid = (start + end)/2; meight be poosible that (start + end) exceeds
// range of integer in java
int mid = start + (end - start) / 2;
if (target < nums[mid]) {
end = mid - 1;
} else if (target > nums[mid]) {
start = mid + 1;
} else {
// petential ans found
ans = mid;
if(findStartIndex){
end = mid -1;
} else {
start = mid +1;
}
}
}
return ans;
}
}
public class Binary {
public static void main(String[] args) {
int[] arr = { 3, 5, 7, 9, 10, 90, 100, 130, 140, 160, 170 };
int target = 10;
System.out.println(ans(arr, target));
}
static int ans(int[] arr, int target) {
// first find the range
// start with the sox of size 2
int start = 0;
int end = 1;
// condition for the target to lie in the range
// while the target element is greater then 'end' keep doubling
while (target > arr[end]) {
int newStart = end + 1;
// double the box value
// end = previous end + sizeofbox *2;
end = end + (end - start + 1) * 2;
start = newStart;
}
return binarySearch(arr, target, start, end);
}
static int binarySearch(int[] arr, int target, int start, int end) {
while (start <= end) {
int mid = start + (end - start) / 2;
if (target < arr[mid])
end = mid - 1;
else if (target > arr[mid])
start = mid + 1;
else
return mid;
}
return -1;
}
}
class Solution {
public int peakIndexInMountainArray(int[] arr) {
int start = 0;
int end = arr.length-1;
while(start<=end){
int mid = start + (end - start)/2;
if(arr[mid+1] > arr[mid]){
start = mid + 1;
} else if(arr[mid+1] < arr[mid]){
return mid;
}else {
end = mid;
}
}
return -1;
}
}
// input
//[0,1,0]
//[0,2,1,0]
//[0,10,5,2]
class Solution {
public int peakIndexInMountainArray(int[] arr) {
int start = 0;
int end = arr.length - 1;
while (start < end) {
int mid = start + (end - start) / 2;
if (arr[mid] > arr[mid + 1]) {
// you are in dexreasing part of array
// so this may be the ans, but look at left
end = mid;
} else {
// you are in ascending part of array
start = mid + 1; // because we know that mid+1 element > mid element
}
}
// in the end, start == end and pointing to the largest number because of the 2
// checks above
// start and end are always trying to find max element in the above 2 checks
// hence, when they are pointing to just one element, that is the max one
// because that is what the checks say
// more elaboration: at every point of time for start and end, they have the
// best possible answer till that time
// and if we are saying that only one item is remaining, hence cuz of above line
// that is the best possible ans
return start; // or return end as both are =
}
}
Q→ Find in mountain array This code is not submitted to leetcode as it need some modifications.
class Solution {
public int search(int[] arr, int target){
int peak = peakIndexInMountainArray(arr);
int firstTry = orderAgnosticBS(arr, target, 0, peak);
if(firstTry != -1){
return firstTry;
}
// try to search in second half
return orderAgnosticBS(arr, target, peak+1, arr.length-1);
}
public int peakIndexInMountainArray(int[] arr) {
int start = 0;
int end = arr.length - 1;
while (start < end) {
int mid = start + (end - start) / 2;
if (arr[mid] > arr[mid + 1]) {
end = mid;
} else {
start = mid + 1;
}
}
return start;
}
static int orderAgnosticBS(int[] arr, int target, int start, int end) {
// find whether the array is sorted in ascending or descending
boolean isAsc = arr[start] < arr[end];
while (start <= end) {
int mid = start + (end - start) / 2;
if (arr[mid] == target)
return mid;
if (isAsc) {
if (target < arr[mid])
end = mid - 1;
else
start = mid + 1;
} else {
if (target > arr[mid])
end = mid - 1;
else
start = mid + 1;
}
}
return -1;
}
}
public class RBS {
public static void main(String[] args) {
int[] arr = { 1, 2, 3, 4, 5, 5, 6 };
System.out.println(findPivotWithDuplicates(arr));
}
static int search(int[] nums, int target) {
int pivot = findPivot(nums);
// if you did not find a pivot, it means the array is not rotated
if (pivot == -1) {
// just do normal binary search
return binarySearch(nums, target, 0, nums.length - 1);
}
// if pivot is found, you have found 2 asc sorted arrays
if (nums[pivot] == target) {
return pivot;
}
if (target >= nums[0]) {
return binarySearch(nums, target, 0, pivot - 1);
}
return binarySearch(nums, target, pivot + 1, nums.length - 1);
}
static int binarySearch(int[] arr, int target, int start, int end) {
while (start <= end) {
// find the middle element
// int mid = (start + end) / 2; // might be possible that (start + end) exceeds
// the range of int in java
int mid = start + (end - start) / 2;
if (target < arr[mid]) {
end = mid - 1;
} else if (target > arr[mid]) {
start = mid + 1;
} else {
// ans found
return mid;
}
}
return -1;
}
// this will not work in duplicate values
static int findPivot(int[] arr) {
int start = 0;
int end = arr.length - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
// 4 cases over here
if (mid < end && arr[mid] > arr[mid + 1]) {
return mid;
}
if (mid > start && arr[mid] < arr[mid - 1]) {
return mid - 1;
}
if (arr[mid] <= arr[start]) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return -1;
}
static int findPivotWithDuplicates(int[] arr) {
int start = 0;
int end = arr.length - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
// 4 cases over here
if (mid < end && arr[mid] > arr[mid + 1]) {
return mid;
}
if (mid > start && arr[mid] < arr[mid - 1]) {
return mid - 1;
}
// if elements at middle, start, end are equal then just skip the duplicates
if (arr[mid] == arr[start] && arr[mid] == arr[end]) {
// skip the duplicates
// NOTE: what if these elements at start and end were the pivot??
// check if start is pivot
if (start < end && arr[start] > arr[start + 1]) {
return start;
}
start++;
// check whether end is pivot
if (end > start && arr[end] < arr[end - 1]) {
return end - 1;
}
end--;
}
// left side is sorted, so pivot should be in right
else if (arr[start] < arr[mid] || (arr[start] == arr[mid] && arr[mid] > arr[end])) {
start = mid + 1;
} else {
end = mid - 1;
}
}
return -1;
}
}
Q→ Find how many times a given array is rotated
public class Binary {
public static void main(String[] args) {
int[] arr = { 4, 5, 6, 7, 0, 1, 2 };
System.out.println(countRotations(arr));
}
private static int countRotations(int[] arr) {
int pivot = findPivot(arr);
return pivot + 1;
}
// this will not work in duplicate values
// use this for non duplicates
static int findPivot(int[] arr) {
int start = 0;
int end = arr.length - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
// 4 cases over here
if (mid < end && arr[mid] > arr[mid + 1]) {
return mid;
}
if (mid > start && arr[mid] < arr[mid - 1]) {
return mid - 1;
}
if (arr[mid] <= arr[start]) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return -1;
}
// use this when there are duplicates
static int findPivotWithDuplicates(int[] arr) {
int start = 0;
int end = arr.length - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
// 4 cases over here
if (mid < end && arr[mid] > arr[mid + 1]) {
return mid;
}
if (mid > start && arr[mid] < arr[mid - 1]) {
return mid - 1;
}
// if elements at middle, start, end are equal then just skip the duplicates
if (arr[mid] == arr[start] && arr[mid] == arr[end]) {
// skip the duplicates
// NOTE: what if these elements at start and end were the pivot??
// check if start is pivot
if (start < end && arr[start] > arr[start + 1]) {
return start;
}
start++;
// check whether end is pivot
if (end > start && arr[end] < arr[end - 1]) {
return end - 1;
}
end--;
}
// left side is sorted, so pivot should be in right
else if (arr[start] < arr[mid] || (arr[start] == arr[mid] && arr[mid] > arr[end])) {
start = mid + 1;
} else {
end = mid - 1;
}
}
return -1;
}
}
public class SplitArray {
public static void main(String[] args) {
}
public int splitArray(int[] nums, int m) {
int start = 0;
int end = 0;
for (int i = 0; i < nums.length; i++) {
start = Math.max(start, nums[i]); // in the end of the loop this will contain the max item of the array
end += nums[i];
}
// binary search
while (start < end) {
// try for the middle as potential ans
int mid = start + (end - start) / 2;
// calculate how many pieces you can divide this in with this max sum
int sum = 0;
int pieces = 1;
for(int num : nums) {
if (sum + num > mid) {
// you cannot add this in this subarray, make new one
// say you add this num in new subarray, then sum = num
sum = num;
pieces++;
} else {
sum += num;
}
}
if (pieces > m) {
start = mid + 1;
} else {
end = mid;
}
}
return end; // here start == end
}
}
