# Clever idea making it simple

• This very nice idea is from rantos22's solution who sadly only commented "You are not expected to understand that :)", which I guess is the reason it's now it's hidden among the most downvoted solutions. I present an explanation and a more usual implementation.

Explanation

Let's say `nums` looks like this: [12, 13, 14, 15, 16, 17, 18, 19, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

Because it's not fully sorted, we can't do normal binary search. But here comes the trick:

• If target is let's say 14, then we adjust `nums` to this, where "inf" means infinity:
[12, 13, 14, 15, 16, 17, 18, 19, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf]

• If target is let's say 7, then we adjust `nums` to this:
[-inf, -inf, -inf, -inf, -inf, -inf, -inf, -inf, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

And then we can simply do ordinary binary search.

Of course we don't actually adjust the whole array but instead adjust only on the fly only the elements we look at. And the adjustment is done by comparing both the target and the actual element against nums[0].

Code

If `nums[mid]` and `target` are "on the same side" of `nums[0]`, we just take `nums[mid]`. Otherwise we use -infinity or +infinity as needed.

``````int search(vector<int>& nums, int target) {
int lo = 0, hi = nums.size();
while (lo < hi) {
int mid = (lo + hi) / 2;

double num = (nums[mid] < nums[0]) == (target < nums[0])
? nums[mid]
: target < nums[0] ? -INFINITY : INFINITY;

if (num < target)
lo = mid + 1;
else if (num > target)
hi = mid;
else
return mid;
}
return -1;
}``````

• Thanks Stefan for the explanation, you're always the best.

• Wow, this is the true solution.

• It can be a follow up of find minimum in rotated array -:)

• thumb up!very clever solution.

• Java version

``````public int search(int[] nums, int target) {
int lo = 0, hi = nums.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;

int num = nums[mid];
// If nums[mid] and target are "on the same side" of nums[0], we just take nums[mid].
if ((nums[mid] < nums[0]) == (target < nums[0])) {
num = nums[mid];
} else {
num = target < nums[0] ? Integer.MIN_VALUE : Integer.MAX_VALUE;
}

if (num < target)
lo = mid + 1;
else if (num > target)
hi = mid - 1;
else
return mid;
}
return -1;
}``````

• Inspired by this and @StefanPochmann work here: https://discuss.leetcode.com/topic/34467/pretty-short-c-java-ruby-python

We can also view the array as already sorted with the following transformation:

``````tuple: (value less than nums[0]?, value)
[1,2,3,4,5] -> [(0,1), (0,2), (0,3), (0,4), (0,5)]
[5,1,2,3,4] -> [(0,5), (1,1), (1,2), (1,3), (1,4)]
``````

Then we can use our standard binary search like so:

``````    def search(self, nums, target):
N, t = nums, target
i = bisect.bisect_left([(x < N[0], x) for x in N], (t < N[0], t))
return i if t in N[i:i+1] else -1
``````

But that's already O(n) for the transform so ...:

``````    def search(self, nums, target):
lo, hi, t = 0, len(nums) - 1, (target < nums[0], target)
while lo <= hi:
mid = (lo + hi) // 2
guess = (nums[mid] < nums[0], nums[mid])
if   guess == t: return mid
elif guess < t:  lo = mid + 1
else:            hi = mid - 1
return -1
``````

• you always make it clear, 3ku

• Rewrite Stefan's algorithm in Java. Hope to make it a little simpler without losing its beauty.

``````    public int search(int[] nums, int target) {
int n = nums.length;
if (n == 0) return -1;

int lo = 0, hi = n - 1, mid = 0, num = 0;
while (lo <= hi) {
mid = (lo + hi) >> 1;
if (nums[mid] == target) return mid;
if ((nums[mid] < nums[0]) ^ (target < nums[0]))
nums[mid] = target < nums[0]? Integer.MIN_VALUE : Integer.MAX_VALUE;

if (nums[mid] < target) lo = mid + 1;
else hi = mid - 1;
}

return -1;
}``````

• if ((nums[mid] < nums[0]) ^ (target < nums[0]))

Great idea to use ^

• Is there an assumption that the array doesn't contain repeated numbers? If the given array is [9, 2, 9, 9, 9, 9, 9] and the target is 2, this algorithm returns -1.

• @da.lin.1232 Hello,
If we we are looking for Integer.MAX_VALUE, the result is wrong.
I think Long is required.

• @StefanPochmann Thanks for the explanation! It makes sense.
I translated your code to python, but it doesn't seem to work (fails on case [3,1]
,3) Could you see why? Here's my code:

``````    def search(self, nums, target):
low = 0
high = len(nums)
while low < high:
#middle = low + (high - low)/2
middle = (low + high) / 2
current = nums[middle] if (nums[middle] > nums[0])==(target > nums[0]) else (-float('inf') if target < nums[0] else float('inf'))
if current < target:
low = middle + 1
elif current > target:
high = middle
else:
return middle
return -1

``````

Thanks.

• @yujiehuang get rid of else statement and insert the following right after you initialize middle--->
if nums[middle]==target:return middle

• This is an excellent solution. The only problem is that it misses the case that one of the number in the array is actually -inf or inf. I am not a python expert, but in case of Java if you are using Integer.MAX_VALUE or Integer.MIN_VALUE, it will be a problem.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.