int find2(Integer[] rotArr, Integer key) {
		int lo = 0;
		int hi = rotArr.length - 1;

		// binary search
		while (lo <= hi) {
			int mid = (lo + hi) / 2;

			// found the key
			if (rotArr[mid] == key)
				return mid;

			// determine where the key should fall into, the left side or the
			// right side. check http://yes.sureinterview.me/shwqst/542002
			if (rotArr[lo] < rotArr[mid]) {
				if (rotArr[lo] <= key && key < rotArr[mid]) {
					hi = mid - 1;
				} else {
					lo = mid + 1;
				}
			} else if (rotArr[lo] > rotArr[mid]) {
				if (rotArr[mid] < key && key <= rotArr[hi]) {
					lo = mid + 1;
				} else {
					hi = mid - 1;
				}
			} else {
				/*
				 * special handing rotArr[lo] == rotArr[mid] == rotArr[hi].
				 * check lo and advance one element.
				 */
				if (rotArr[lo] == key)
					return lo;
				lo++;
			}
		}
		return -1;
	}