Binary search with bunch of if statements


  • 0
    S

    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;
    }

  • 0
    A
      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.


  • 1
    R
    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];
    }
    

    }


  • 0
    C
    This post is deleted!

  • 0
    S

    Please use English. Thanks.


  • 2
    C
    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.


  • 0
    J

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


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

    may overflow


  • 0
    R

    Good evening dance:

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


  • 0
    Y

    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.


  • 0
    R

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


Log in to reply
 

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