Iterative binary search in one pass O(log(n)) - With explanation


  • 0
    A
    class Solution {
    public:
        int searchInsert(vector<int>& nums, int target) {
            int s = 0, e = nums.size()-1,m;
    
           // Invariant for binary search
            while(e>=s){
               // Midpoint formula to avoid overflow
                m = s + (e-s)/2;
    
                // while searching, return the index if target is found OR 
                // check if the present element is greater than target and prev element 
                // is smaller(or equal to, but since no duplicates, we can avoid that confusion) 
                // than target(also ensure that it is not at the beginning of range 
                // by checking m == s)
                if(nums[m] == target || (nums[m] > target && (m == s || nums[m-1] < target))) return m;
                
                //Update the range on binary search
                else if(nums[m] < target) s = m + 1;
                else e = m - 1;
            }
            
            // If target is greater than largest element in array, then insert it beyond the last position
            return nums.size();
        }
    };

Log in to reply
 

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