Accepted C++ Solution in 6ms (Clean Modified Binary Search)


  • 0

    My solution is a simple/clean modification on the O(logN) binary search algorithm, instead of returning a bool we break the search (or while loop) and if the mid contains the target, return mid, else return mid + 1:

    int modifiedBinarySearch(vector<int>& nums, int target) {
    	int lb = 0;
    	int ub = nums.size();
    	int mid = (lb + ub) / 2;
    	if (ub == 0) return 0;
    
    	while (true) {
    		mid = (lb + ub) / 2;
    		if (nums[mid] == target) break;
    		if (ub - lb < 2) break;
    		if (target > nums[mid]) lb = mid;
    		else ub = mid;
    	}
    
    	if (target <= nums[mid]) return mid;
    	else return mid + 1;
    }
    
    int searchInsert(vector<int>& nums, int target) {
            return modifiedBinarySearch(nums, target);
    }
    

Log in to reply
 

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