# Revised Binary Search

• ``````public class Solution {
public int search(int[] A, int target) {
int lo = 0;
int hi = A.length - 1;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (A[mid] == target) return mid;

if (A[lo] <= A[mid]) {
if (target >= A[lo] && target < A[mid]) {
hi = mid - 1;
} else {
lo = mid + 1;
}
} else {
if (target > A[mid] && target <= A[hi]) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
}
return A[lo] == target ? lo : -1;
}
``````

}

• Notice that there is always a half of the array sorted, so we only need to see whether the target is in the sorted part or rotated part

• Good! Your solution is more simple than mine! I spend two much to see whether the target is in the sorted part or not

• Hi I used almost the same solution as yours, except written in python. But it seems to be extremly slow in the scoreboard(beat 20% submission). Is that the same case for you?

• same idea! python version

``````def search(self, nums, target):
l, r = 0, len(nums)
while l < r:
mid = (l + r) / 2
if nums[mid] == target: return mid
if target > nums[mid]:
if nums[mid] < nums[0] and target >= nums[0]:
r = mid
else:
l = mid + 1
else:
if nums[mid] >= nums[0] and target < nums[0]:
l = mid + 1
else:
r = mid
return -1``````

• If you change your while condition to lo<=hi, then you will simply need to return just -1 in the end.

• @jerry13466 said in Revised Binary Search:

int mid = (lo + hi) / 2;

It would be better to use

int mid = lo + (hi - lo) / 2;

because if lo and hi are very large, (lo + hi) might potentially cause overflow.

• Same idea here but without that many conditionals:

``````public class Solution {
public int search(int[] nums, int target) {
int lo = 0, hi = nums.length - 1;

while(lo <= hi) {
int mid = lo + (hi - lo) / 2;
if(nums[mid] == target) return mid;
if(nums[lo] <= target && target < nums[mid]
|| (nums[mid] < nums[hi] && (target > nums[hi] || target < nums[mid]))) {
hi = mid - 1;
}else{
lo = mid + 1;
}
}

return -1;
}
}
``````

• Javascript version:

``````var search = function(nums, target) {
if(nums.length == 0) return -1;
var lo = 0, hi = nums.length - 1;
var A = nums;
while(lo < hi) {
var mid = ((lo + hi) / 2) | 0;
if(A[mid] == target) return mid;

if(A[lo] <= A[mid]) {
if(target >= A[lo] && target < A[mid]) {
hi = mid -1;
} else {
lo = mid + 1;
}
} else {
if(target > A[mid] && target <= A[hi]) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
}
return A[lo] == target ? lo : -1;
};
``````

• @jerry13466 Somehow this now gives ArrayIndexOutOfBoundsException for the return statement.

• @BryanBo.Cao Tried this, but it goes TLE for input [1, 3] 2

• Thanks @jerry13466

Quick question, why do you have the = sign in if (A[lo] <= A[mid]) (so covering the equal case in the if clause vs. the else clause). I tried without the equal sign and it does not work for some edge cases but I want to know your reasoning behind this.

• @tuanledang1120

I have this question too! When right==left + 1, we will get mid == left. And we have already checked if nums[mid] == target, so at that time nums[right] is to be checked. At chat time, target >= nums[left] && target < nums[mid] and target > nums[mid] && target <= nums[right] are both false. We need left++ so we put the = at nums[left] <= nums[mid].

And I have test if I change mid = (left + right) / 2 to mid = (left + right + 1) / 2, put = to the other inequality is OK.

• ``````if (nums == null || nums.length == 0) {
return -1;
}
``````

I think this code should be added in order to avoid ArrayIndexOutOfBoundsException.

• @nvinchh add this,then it will work.

``````if (nums == null || nums.length == 0) {
return -1;
}
``````

• @jerry13466 emm... I guess you should take that the array is empty into consideration.

• This post is deleted!

• @jerry13466 the same idea.

``````class Solution {
public int search(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return -1;
}

int start = 0;
int end = nums.length - 1;

while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (nums[mid] > nums[start]) {
if (nums[start] <= target && nums[mid] >= target) {
end = mid;
}
else {
start = mid;
}
}
else {
if (nums[mid] <= target && nums[end] >= target) {
start = mid;
}
else {
end = mid;
}
}
}

if (nums[start] == target) {
return start;
}
if (nums[end] == target) {
return end;
}
return -1;
}
}``````

• @showskyzt Thanks for your explanation! But I still cannot understand why "target > nums[mid] && target <= nums[right]" is false. In this case, left + 1 == right, so the first condition is false, but for the second, target > nums[left] && target <= nums[right] can happen, in this case, target == nums[right].
------------UPDATE-----------------
OK, I think you put an assumption that target < nums[left]

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