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

  • 0
    class Solution {
        int searchInsert(vector<int>& nums, int target) {
            int s = 0, e = nums.size()-1,m;
           // Invariant for binary search
               // 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.