int find(Integer[] rotArr, Integer key, Integer lo, Integer hi) {
		// if the array has a break point, mapping the hi index to the right.
		// for example, if the rotated array is {3,4,1,2}, imagine the array is
		// extended as {3,4,1,2, 3,4,1,2}
		int length = rotArr.length;
		if (hi < lo) {
			hi += length;
		}

		// binary search.
		while (hi >= lo) { // the minimum sub array is empty.
			int mid = (lo + hi) / 2;
			Integer midVal = rotArr[mid % length];

			// found the key
			if (midVal == key)
				return mid % length;

			if (midVal > key) {
				// lower the high boundary.
				hi = mid - 1;
			} else {
				// raise the low boundary.
				lo = mid + 1;
			}
		}
		// when return, the subarray rotArr[ lo...hi ] is empty.
		return -1;
	}