My accepted simple solution based on binary search,Any advising?


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

  • 0
    C

    A Little Advise: you can use "mid = low + (high-low)/2;" to replace "mid = (low+high)/2;"


  • 0
    H

    Do you mind explaining your advise a little bit? thanks in advance.


  • 0
    C

    It is just a small trick .
    When low and high is very large,calculate (low+high) will be out of range,then the result will be wrong.
    So change it to (low + (high-low)/2 ).
    But it does'n matter in this problem.


Log in to reply
 

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