Binary search with bunch of if statements

• This is the what I came up with. using binary search with bunch of testings. Can you guys please comment on my code?

``````public int searchInsert(int[] A, int target) {
if (A.length == 0 || A[0] >= target)
return 0;
if (target > A[A.length-1])
return A.length;
int start = 0;
int end = A.length-1;

while (start < end) {
int mid = (start + end) / 2;
if (A[mid] == target)
return mid;
if (A[mid] < target && target <= A[mid+1])
return mid+1;
if (A[mid] > target)
end = mid;
else
start = mid + 1;
}
return 0;
}``````

• ``````  public int searchInsert(int[] A, int target) {
return helper(A, target, 0, A.length - 1);
}
public int helper(int[] A, int target, int start, int end) {
if (target == A[(start + end)/2]) return (start + end)/2;
else if (end - start <= 1) {
if (target < A[start]) return start;
else if (target > A[end]) return end + 1;
else return start + 1;
}
else if (target > A[(start + end)/2]) return helper(A, target, (start + end)/2, end);
else return helper(A, target, start, (start + end)/2);
}
``````

Here is a recursion version.

• ``````public class Solution {
public int searchInsert(int[] A, int target) {
if (null == A) return 0;

int left = 0;
int right = A.length - 1;
int[] location = {0, 0}; // {inOrNot, targetedPosition}

// binary search
while(left <= right){
int middle = (left + right) >> 1;  // middle = left + (right - left) / 2 will be safer
if (target == A[middle] ) { // good morning, baby~
location[0] = 1;
location[1] = middle;
break;
}else if (target < A[middle]) {
right = middle - 1;
}else {
left = middle + 1;
}
}

if (0 == location[0]) { // A doesn't contain the target
location[1] = left; // so, the target will be put @ "left"
}

return location[1];
}
``````

}

• This post is deleted!

• Please use English. Thanks.

• ``````class Solution {
public:
int searchInsert(int A[], int n, int target) {
int a,b;
a=0;b=n-1;
while (a<=b){   //binary search
int c=a+((b-a)>>1);
if (A[c]>target) b=c-1;
else if (A[c]<target) a=c+1;
else return c;
}
//If target is not found,the target will be in (b,a).so a is the anwser.
return a;
}
};
``````

My solution.

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

• ``````    int middle = (left + right) >> 1;
``````

may overflow

• Good evening dance:

Why this may overflow? It's the same as: middle = (left + right) / 2

• My guess is (left + right) may get too large. Using middle = left + (right - left) / 2 would be safer. justdance please correct me if I'm wrong.

• Really really thank you. I think you are right.
I never thought of this.

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