Binary Search, Limit Search, Bound Search and Range Query

Binary Search

Binary Search is the most efficient algorithm for searching in sorted array.

Implementation of Binary Search is pretty straightforward.

	//----------------------------------------------------------------------------------
	/**
	* Searches searchItem in the array using iterative binary search
	* @param a
	* @param searchItem
	* @return
	*/
	public static int search(int[] a, int searchItem) {
	int lo = 0;
	int hi = a.length - 1;
	while (lo <= hi) {
	int mid = (lo + hi) / 2;
	if(a[mid] == searchItem) return mid;
	else if(a[mid] > searchItem) hi = mid - 1;
	else lo = mid + 1;
	}
	return -1;
	} // search
	//------------------------------------------------------------------------------------

view raw BinarySearch.java hosted with ❤ by GitHub

Lower Limit and Upper Limit

Binary search in a sorted list is straight forward. Binary search principle can also be applied to search for the lower limit and upper limit.

Lower Limit means the minimum index item, which is greater than or equal to the given search item.

Similarly, Upper Limit means the maximum index item, which less than or equal to the given search item.

Lower Limit

	//------------------------------------------------------------------------------------
	/**
	* Lower limit is the number greater than or equal to searchItem with minimum index in the array
	* @param a
	* @param searchItem
	* @return
	*/
	public static int searchLowerLimit(int[] a, int searchItem) {
	int lo = 0;
	int hi = a.length-1;
	if (hi == -1 || a[hi] < searchItem) { // no greater item, all items in the array are smaller than searchItem
	return -1;
	}
	while (lo <= hi) {
	int mid = (lo + hi)/2;
	if(a[mid] >= searchItem) {
	hi = mid - 1;
	} else {
	lo = mid + 1;
	}
	}
	return hi + 1;
	} // searchLowerLimit
	//------------------------------------------------------------------------------------

view raw BinarySearch.java hosted with ❤ by GitHub

Upper Limit

	//------------------------------------------------------------------------------------
	/**
	* Upper limit is the number smaller than or equal to searchItem with maximum index in the array
	* @param a
	* @param searchItem
	* @return
	*/
	public static int searchUpperLimit(int[] a, int searchItem) {
	int lo = 0;
	int hi = a.length - 1;
	if (hi == -1 || a[0] > searchItem) { // no smaller item, all items in the array are greater than searchItem
	return -1;
	}
	while (lo <= hi) {
	int mid = (lo + hi)/2;
	if(a[mid] > searchItem) hi = mid - 1;
	else lo = mid + 1;
	}
	return lo - 1;
	} // searchUpperLimit
	//------------------------------------------------------------------------------------

view raw BinarySearch.java hosted with ❤ by GitHub

Lower Bound and Upper Bound

Lower Bound means the minimum index item, which is greater than given search item.

Similarly, Upper Limit means the maximum index item, which less than given search item.

Lower Bound

	//------------------------------------------------------------------------------------
	/**
	* Lower Bound is the number strictly greater than searchItem with minimum index in the array
	*
	* Only two changes required from above method
	* 1. if (hi == -1 || a[hi] < searchItem) ==> if (hi == -1 || a[hi] <= searchItem)
	* 2. if(a[mid] >= searchItem) ==> if(a[mid] > searchItem) {
	* @param a
	* @param searchItem
	* @return
	*/
	public static int searchLowerBound(int[] a, int searchItem) {
	int lo = 0;
	int hi = a.length-1;
	if (hi == -1 || a[hi] <= searchItem) { // no greater item, all items in the array are smaller than searchItem
	return -1;
	}
	while (lo <= hi) {
	int mid = (lo + hi)/2;
	if(a[mid] > searchItem) {
	hi = mid - 1;
	} else {
	lo = mid + 1;
	}
	}
	return hi + 1;
	} // searchLowerLimit
	//------------------------------------------------------------------------------------

view raw BinarySearch.java hosted with ❤ by GitHub

Upper Bound

	//------------------------------------------------------------------------------------
	/**
	* Upper limit is the number strictly smaller than searchItem with maximum index in the array
	*
	* Only two changes required in above method
	* 1. if (hi == -1 || a[0] > searchItem) ==> if (hi == -1 || a[0] >= searchItem)
	* 2. if(a[mid] > searchItem) ==> if(a[mid] >= searchItem)
	* @param a
	* @param searchItem
	* @return
	*/
	public static int searchUpperBound(int[] a, int searchItem) {
	int lo = 0;
	int hi = a.length - 1;
	if (hi == -1 || a[0] >= searchItem) { // no smaller item, all items in the array are greater than searchItem
	return -1;
	}
	while (lo <= hi) {
	int mid = (lo + hi)/2;
	if(a[mid] >= searchItem) hi = mid - 1;
	else lo = mid + 1;
	}
	return lo - 1;
	} // searchUpperBound
	//------------------------------------------------------------------------------------

view raw BinarySearch.java hosted with ❤ by GitHub

Test

	public static void main(String[] args) {
	//0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
	int[] list = new int[]{1, 2, 5, 12, 17, 23, 24, 26, 45, 55, 77, 89, 91, 93, 95, 100, 113};
	verify(5, search(list, 23));
	verify(5, search(list, 23));
	verify(8, search(list, 45));
	verify(10, search(list, 77));
	verify(-1, search(list, 78));
	verify(14, search(list, 95));
	verify(16, search(list, 113));
	verify(0, search(list, 1));
	verify(-1, search(list, 3));
	verify(0, search(new int[]{3}, 3));
	verify(-1, search(new int[]{}, 3));
	verify(-1, search(new int[]{3}, 4));
	//0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
	list = new int[]{1, 1, 1, 1, 2, 2, 3, 3, 3, 3, 4, 5, 8, 9, 10, 11, 11, 11, 33, 33, 44, 75, 87, 87, 87, 90, 90, 90, 90, 100};
	// Lower Limit Search
	verify(18, searchLowerLimit(list, 23));
	verify(0, searchLowerLimit(list, 1));
	verify(25, searchLowerLimit(list, 90));
	verify(29, searchLowerLimit(list, 100));
	verify(-1, searchLowerLimit(list, 101));
	verify(-1, searchLowerLimit(new int[]{}, 101));
	verify(0, searchLowerLimit(new int[]{10}, 9));
	verify(-1, searchLowerLimit(new int[]{10}, 11));
	// Lower Bound
	verify(29, searchLowerBound(list, 90));
	verify(12, searchLowerBound(list, 5));
	verify(-1, searchLowerBound(list, 100));
	verify(18, searchLowerBound(list, 11));
	verify(18, searchLowerBound(list, 25));
	verify(4, searchLowerBound(list, 1));
	// Upper Limit Search
	verify(17, searchUpperLimit(list, 23));
	verify(3, searchUpperLimit(list, 1));
	verify(28, searchUpperLimit(list, 90));
	verify(29, searchUpperLimit(list, 100));
	verify(29, searchUpperLimit(list, 101));
	verify(-1, searchUpperLimit(new int[]{}, 101));
	verify(-1, searchUpperLimit(new int[]{10}, 9));
	verify(0, searchUpperLimit(new int[]{10}, 11));
	// Upper Bound Search
	verify(17, searchUpperBound(list, 23));
	verify(-1, searchUpperBound(list, 1));
	verify(24, searchUpperBound(list, 90));
	verify(28, searchUpperBound(list, 100));
	verify(29, searchUpperBound(list, 101));
	verify(-1, searchUpperBound(new int[]{}, 101));
	verify(-1, searchUpperBound(new int[]{10}, 9));
	verify(0, searchUpperBound(new int[]{10}, 11));
	} // main
	//----------------------------------------------------------------------------------
	/**
	* Verify expected and actual values
	* @param expected
	* @param actual
	*/
	private static void verify(int expected, int actual) {
	if (expected == actual) {
	//System.out.println("Success");
	} else {
	System.out.println("*** Failed");
	}
	} // verify
	//----------------------------------------------------------------------------------

view raw BinarySearch.java hosted with ❤ by GitHub

Application of Limit Search

There can be several applications of these. One of the application could be using the lower and upper limit to find the number of items in the given range.

	//------------------------------------------------------------------------------------
	/**
	* Finds all the numbers in a sorted array in the given range
	* @param list input sorted array
	* @param @lowerLimit lower limit of the range
	* @param @upperLimit upper limit of the range
	* @return list of numbers in the range
	*/
	public static List findElementsInRange(int[] list, int lowerLimit, int upperLimit) {
	List result = new ArrayList();
	int start = searchLowerLimit(list, lowerLimit);
	if (start == -1) {
	return result;
	}
	int end = searchUpperLimit(list, upperLimit);
	if(end == -1) {
	return result;
	}
	while(start <= end) {
	result.add(list[start++]);
	}
	return result;
	} // findElementesInRange
	//------------------------------------------------------------------------------------

view raw BinarySearch.java hosted with ❤ by GitHub

---

---

---