Back to DSA Course

Binary Search is the process of searching an element from sorted array by dividing the search interval in half.

Binary Search is faster than Linear Search.

Although Binary Search is a very optimized way of searching a particular element but the array must be sorted on which you want to perform search process.

If Array is unsorted then we have to perform the sort first and then we can perform binary search.

Let's start coding for binary search

package com.praveen.search.binary;

public class BinarySearch {
	public static void main(String[] args) {
		int[] arr = { 2, 8, 10, 12, 16, 24, 38, 42, 92, 122 };
		System.out.println(search(arr, 42));
		System.out.println(search(arr, 10));
		System.out.println(search(arr, 100));
		System.out.println(search(arr, 16));

	}

	public static int search(int[] arr, int target) {

		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 -1;

	}

}

Output

7
2
-1
4

Order Agnositic Binary Search

If we dont know in which order the array is provided then how we can apply the binary search logic.

Here we go, we just need to compare the first and last element in array and then decide whether array is in ascending or descending order.

Let's code now.

package com.praveen.search.binary;

public class OrderAgnosticBS {

	public static void main(String[] args) {
		System.out.println(orderAgnosticBS(new int[] { 2, 8, 10, 12, 16, 24, 38, 42, 92, 122 }, 42));
		System.out.println(orderAgnosticBS(new int[] { 2, 8, 10, 12, 16, 24, 38, 42, 92, 122 }, 10));
		System.out.println(orderAgnosticBS(new int[] { 2, 8, 10, 12, 16, 24, 38, 42, 92, 122 }, 100));
		System.out.println(orderAgnosticBS(new int[] { 2, 8, 10, 12, 16, 24, 38, 42, 92, 122 }, 16));
		System.out.println(orderAgnosticBS(new int[] { 122, 92, 42, 38, 24, 16, 12, 10, 8, 2 }, 42));
		System.out.println(orderAgnosticBS(new int[] { 122, 92, 42, 38, 24, 16, 12, 10, 8, 2 }, 10));
		System.out.println(orderAgnosticBS(new int[] { 122, 92, 42, 38, 24, 16, 12, 10, 8, 2 }, 100));
		System.out.println(orderAgnosticBS(new int[] { 122, 92, 42, 38, 24, 16, 12, 10, 8, 2 }, 16));
	}

	private static int orderAgnosticBS(int[] arr, int target) {

		int start = 0;
		int end = arr.length - 1;

		// find whether array is 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;

	}

}

Output

7
2
-1
4
2
7
-1
5

Let's see some programs

1.Find the ceiling of a number

package com.praveen.search.binary;

/*
 Ceiling -> Find the smallest element in an array greater or equal to target
 */
public class Ceiling {

	public static void main(String[] args) {

		System.out.println(ceiling(new int[] { 2, 3, 5, 9, 18, 24, 36, 72 }, 55));
		System.out.println(ceiling(new int[] { 2, 3, 5, 9, 18, 24, 36, 72 }, 18));
		System.out.println(ceiling(new int[] { 2, 3, 5, 9, 18, 24, 36, 72 }, 6));

	}

	private static int ceiling(int[] arr, int target) {

		int start = 0;
		int end = arr.length - 1;

		while (start <= end) {
			int mid = start + (end - start) / 2;

			if (target == arr[mid]) {
				return target;
			} else if (target > arr[mid]) {
				start = mid + 1;
			} else if (target < arr[mid]) {
				end = mid - 1;
			}

		}
		return arr[start];
	}

}

Output

72
18
9

2.Find the floor of a number

package com.praveen.search.binary;

/*
Floor -> Find the greater element in an array smaller or equal to target
*/
public class Floor {

	public static void main(String[] args) {
		System.out.println(floor(new int[] { 2, 3, 5, 9, 18, 24, 36, 72 }, 55));
		System.out.println(floor(new int[] { 2, 3, 5, 9, 18, 24, 36, 72 }, 18));
		System.out.println(floor(new int[] { 2, 3, 5, 9, 18, 24, 36, 72 }, 6));
	}
	
	private static int floor(int[] arr, int target) {

		int start = 0;
		int end = arr.length - 1;

		while (start <= end) {
			int mid = start + (end - start) / 2;

			if (target == arr[mid]) {
				return target;
			} else if (target > arr[mid]) {
				start = mid + 1;
			} else if (target < arr[mid]) {
				end = mid - 1;
			}

		}
		return arr[end];
	}


}

Output

36
18
5

3.Find Smallest Letter Greater Than Target

package com.praveen.search.binary;
public class NextGreatestLetter {

	public static void main(String[] args) {

		System.out.println(nextGreatestLetter(new char[] { 'c', 'f', 'j' }, 'a'));
		System.out.println(nextGreatestLetter(new char[] { 'c', 'f', 'j' }, 'c'));
		System.out.println(nextGreatestLetter(new char[] { 'c', 'f', 'j' }, 'd'));
	}

	private static char nextGreatestLetter(char[] letters, char target) {
		int start = 0;
		int end = letters.length - 1;
		while (start <= end) {
			int middle = start + ((end - start) / 2);
			if (letters[middle] > target) {
				end = middle - 1;
			} else {
				start = middle + 1;
			}
		}
		if (start == letters.length)
			return letters[0];
		return letters[start];
	}

}

Output

c
f
f

4.Find First and Last Position of Element in Sorted Array

package com.praveen.search.binary;

import java.util.Arrays;

public class SearchInRange {

	public static void main(String[] args) {

		System.out.println(Arrays.toString(searchRange(new int[] {5,7,7,8,8,10},8)));
		System.out.println(Arrays.toString(searchRange(new int[] {5,7,7,8,8,10},6)));
		System.out.println(Arrays.toString(searchRange(new int[] {},0)));
		System.out.println(Arrays.toString(searchRange(new int[] {5,7,7,8,8,10},7)));
	}

	private static int[] searchRange(int[] nums, int target) {
		int[] ans = { -1, -1 };
		int start = search(nums, target, true);
		int end = search(nums, target, false);

		ans[0] = start;
		ans[1] = end;

		return ans;

	}

	private static int search(int[] nums, int target, boolean firstStartIndex) {

		int start = 0;
		int end = nums.length - 1;
		int ans = -1;

		while (start <= end) {
			int mid = start + (end - start) / 2;

			if (target == nums[mid]) {
				ans = mid;
				if (firstStartIndex) {
					end = mid - 1;
				} else {
					start = mid + 1;
				}
			} else if (target > nums[mid]) {
				start = mid + 1;
			} else if (target < nums[mid]) {
				end = mid - 1;
			}
		}

		return ans;

	}
}

Output

[3, 4]
[-1, -1]
[-1, -1]
[1, 2]

5.Find position of an element in a sorted array of infinite numbers

package com.praveen.search.binary;

public class InfiniteArray {

	public static void main(String[] args) {

		int[] arr = { 3, 5, 7, 9, 10, 90, 100, 130, 140, 160, 170 };

		System.out.println(ans(arr, 10));

	}

	private static int ans(int[] arr, int target) {
		int start = 0;
		int end = 1;
		while (target > arr[end]) {

			int temp = end + 1;
			end = end + (end - start + 1) * 2;
			start = temp;

		}

		return search(arr, target, start, end);
	}

	private static int search(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;
	}

}

Output

4

6.Peak Index in a Mountain Array

package com.praveen.search.binary;

public class Mountain {

	public static void main(String[] args) {

		System.out.println(peakIndexInMountainArray(new int[] { 0, 1, 0 }));
		System.out.println(peakIndexInMountainArray(new int[] { 0, 2, 1, 0 }));
		System.out.println(peakIndexInMountainArray(new int[] { 0, 10, 5, 2 }));

	}

	private static 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;
	}

}

Output

1
1
1

7.Search in Rotated Sorted Array

package com.praveen.search.binary;

public class SearchInRotatedSortedArray {

	public static void main(String[] args) {
		System.out.println(search(new int[] { 4, 5, 6, 7, 0, 1, 2 }, 0));
		System.out.println(search(new int[] { 4, 5, 6, 7, 0, 1, 2 }, 3));
		System.out.println(search(new int[] { 1 }, 0));

	}

	private static int search(int[] nums, int target) {
		int i = 0;
		int j = nums.length - 1;
		while (i <= j) {
			int mid = (i + j) / 2;
			if (nums[mid] == target)
				return mid;
			else if (nums[i] <= nums[mid]) {
				if (nums[i] <= target && nums[mid] > target) {
					j = mid - 1;
				} else {
					i = mid + 1;
				}
			} else if (nums[mid] <= nums[j]) {
				if (nums[mid] < target && nums[j] >= target) {
					i = mid + 1;
				} else {
					j = mid - 1;
				}
			}
		}
		return -1;
	}
}

Output

4
-1
-1

8.Split Array Largest Sum

package com.praveen.search.binary;

public class SplitArrayLargestSum {

	public static void main(String[] args) {

		System.out.println(splitArray(new int[] { 7, 2, 5, 10, 8 }, 2));
		System.out.println(splitArray(new int[] { 1, 2, 3, 4, 5 }, 2));
		System.out.println(splitArray(new int[] { 1, 4, 4 }, 3));
	}

	private static 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]);
			end += nums[i];
		}

		while (start < end) {
			int mid = start + (end - start) / 2;
			int sum = 0;
			int pieces = 1;
			for (int num : nums) {
				if (sum + num > mid) {
					sum = num;
					pieces++;
				} else {
					sum += num;
				}
			}

			if (pieces > m) {
				start = mid + 1;
			} else {
				end = mid;
			}

		}
		return end;
	}

}

Output

18
9
4

9. Search in 2D Array of equal rows and columns in sorted order

package com.praveen.search.binary;

import java.util.Arrays;

public class RowColMatrix {
	public static void main(String[] args) {
		int[][] arr = { { 10, 20, 30, 40 }, { 15, 25, 35, 45 }, { 28, 29, 37, 49 }, { 33, 34, 38, 50 } };

		System.out.println(Arrays.toString(search(arr, 49)));
		System.out.println(Arrays.toString(search(arr, 25)));
	}

	private static int[] search(int[][] matrix, int target) {
		int r = 0;
		int c = matrix[0].length - 1;

		while (r < matrix.length && c >= 0) {
			if (matrix[r][c] == target) {
				return new int[] { r, c };
			}
			if (matrix[r][c] < target) {
				r++;
			} else {
				c--;
			}
		}
		return new int[] { -1, -1 };
	}
}

Output

[2, 3]
[1, 1]

10. Search in Sorted Matrix

package com.praveen.search.binary;

import java.util.Arrays;

public class SortedMatrix {
	public static void main(String[] args) {
		int[][] arr = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };
		System.out.println(Arrays.toString(search(arr, 9)));
	}

	static int[] binarySearch(int[][] matrix, int row, int cStart, int cEnd, int target) {
		while (cStart <= cEnd) {
			int mid = cStart + (cEnd - cStart) / 2;
			if (matrix[row][mid] == target) {
				return new int[] { row, mid };
			}
			if (matrix[row][mid] < target) {
				cStart = mid + 1;
			} else {
				cEnd = mid - 1;
			}
		}
		return new int[] { -1, -1 };
	}

	static int[] search(int[][] matrix, int target) {
		int rows = matrix.length;
		int cols = matrix[0].length;
		if (cols == 0) {
			return new int[] { -1, -1 };
		}
		if (rows == 1) {
			return binarySearch(matrix, 0, 0, cols - 1, target);
		}

		int rStart = 0;
		int rEnd = rows - 1;
		int cMid = cols / 2;

		while (rStart < (rEnd - 1)) {
			int mid = rStart + (rEnd - rStart) / 2;
			if (matrix[mid][cMid] == target) {
				return new int[] { mid, cMid };
			}
			if (matrix[mid][cMid] < target) {
				rStart = mid;
			} else {
				rEnd = mid;
			}
		}

		if (matrix[rStart][cMid] == target) {
			return new int[] { rStart, cMid };
		}
		if (matrix[rStart + 1][cMid] == target) {
			return new int[] { rStart + 1, cMid };
		}

		if (target <= matrix[rStart][cMid - 1]) {
			return binarySearch(matrix, rStart, 0, cMid - 1, target);
		}
		if (target >= matrix[rStart][cMid + 1] && target <= matrix[rStart][cols - 1]) {
			return binarySearch(matrix, rStart, cMid + 1, cols - 1, target);
		}
		if (target <= matrix[rStart + 1][cMid - 1]) {
			return binarySearch(matrix, rStart + 1, 0, cMid - 1, target);
		} else {
			return binarySearch(matrix, rStart + 1, cMid + 1, cols - 1, target);
		}
	}
}

Output

[2, 2]