• ``````public boolean search(int[] A, int target) {
int start = 0;
int end = A.length - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (A[mid] == target) // case 0
return true;
// finally start == mid == end, if case 0, return true, else end the loop
else if (A[start] == A[mid])
start++;
else if (A[end] == A[mid])
end--;
else if (A[start] <= target && target <= A[mid]) // case 1
end = mid;
else if (A[mid] < target && target <= A[end]) // case 2
start = mid + 1;
else if (A[start] > A[mid]) // case 2 is false, so target in this range
end = mid;
else   // case A[mid] > A[end] and case 1 is false, similar to above
start = mid + 1;
}
return false;
}``````

• int mid = (start + end ) / 2;

• We don't recommend to write code like this since it may overflow while code like start + (end - start) / 2 won't in any case.

• I am wondering why (start + end ) / 2 would overflow. Given the condition (start <= end),if the array needs to overflow, that means (end+start)/2 > end, which means start/2 > end/2 that's to say start > end. It doesn't follow the condition (start <= end so it will break up the loop.

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