public static int search(int a[], int target) {
		int l=0, u=a.length-1;
		while (l <= u) {
			int m = l + (u-l)/2; // different from book's "(l+u)/2": to prevent overflow
			if (target == a[m]) {
				return m;
			}
			else if (target < a[m]) {
				// normal
				if (target >= a[l] || a[l] >= a[m]) {
					u = m-1;
				}
				else {
					l = m+1;
				}
			}
			else if (target > a[m]) { 
				// normal
				if (target <= a[u] || a[u] <= a[m]) {
					l = m + 1;
				}
				else {
					u = m - 1;
				}
			}
		}
		return -1;
	}