Simple Binary Search Solution


  • 9
    Y

    I think the solution does not need a lot of if statement.
    Only two cases:
    1 if found, just return current index
    2 if not found, return next index where the search end

    int search(int A[], int start, int end, int target) {
        if (start > end) return start;
        int mid = (start + end) / 2;
        if (A[mid] == target) return mid;
        else if (A[mid] > target) return search(A, start, mid - 1, target);
        else return search(A, mid + 1, end, target);
    }
    int searchInsert(int A[], int n, int target) {
        return search(A, 0, n - 1, target);
    }

  • 0
    Y

    You are kind of right. However, I guess an iterative answer has better performance.


  • 1
    R

    My iterative solution

    class Solution {
    public:
        int searchInsert(int A[], int n, int target) {
        	if (!A||n==0) return 0;
        	int low=0,high=n-1;
        	
        	if (A[low]>=target) return low;
        	if (A[high]<target) return high+1;
        	
        	while (low<high){
        		int mid=low+(high-low)/2;
        		
        		if (A[mid]<target&&A[mid+1]>=target)
        			return mid+1;
        		else if (A[mid]>=target)
        			high=mid;
        		else if (A[mid+1]<target)
        			low=mid+1;   		
        	}
        	return low;
        }
    };

  • 33
    O

    My iterative java solution

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

    .


  • 0
    K

    my c++ iterative solution is simple:

    class Solution {
    public:
        int searchInsert(int A[], int n, int target) {
            int i = 0 , j = n-1;
            while(i<=j){
                if(target==A[(i+j)/2]) return (i+j)/2;
                if(target<A[(i+j)/2]) j = (i+j)/2-1;
                if(target>A[(i+j)/2]) i = (i+j)/2+1;
            }
            return i>j?i:j;
        }
    };

  • 0
    H

    consider the case [1,3] 4 this code will return 1, which should be 2


  • 0
    L

    the while loop is the key point.


  • 0
    S

    If the sorted array contains duplicate elements, your code might not work. E.g. [3,3,3,3,3], 3


  • 0
    B

    I think it would be better if we compute the mid with start + (end - start) / 2 to avoid possible overflows for int.


  • 0
    L

    Could anyone explain to me why an iterative solution is preferable to a recursive one?


  • 0
    This post is deleted!

  • 0
    O

    It's ok to use hi + 1 instead of lo for the last return statement. But not mid or mid + 1.
    In most of cases mid + 1 will give the correct result, but when the test data only have one element like this [1],0 , mid + 1 would be wrong.


  • 0
    A

    My approach is slightly different. I try to find a number y such that y * y <= x and (y + 1) * (y + 1) > x.

    public class Solution {
        public int sqrt(int x) {
            int left = 1, right = x, mid = 0;
            
            if (x == 1 || x == 0) {return x;}
            
            while (true) {
                mid = (left + right) / 2;
                int a = x / mid;
                int b = x / (mid + 1);
                
                if (mid <= a && mid + 1 > b) {
                    return mid;
                }
                if (mid <= a) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
    }

  • 0
    U

    Firstly, when you use an recursive one, you will use more space, since each time you make a call, you will allocate some space on the stack. And secondly, as I said above, I think allocate a memory may be slower than just assign a new value to an existing variable(variable may be stored in a register).


  • 0
    J

    I don't quite get it. Why (start + end) / 2 might cause overflow?


  • 0
    Y

    If start = end = MAX_INT, (start + end) / 2 overflows while start + (end - start) / 2 doesn't.


  • 0
    J

    Got it. Thanks very much


  • 0
    S

    It's far less intuitive looking than other answers, and I'd be pissed if I came across this in production code. ouchxp is probably the best as far as clean informative code.


Log in to reply
 

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