Quite confused, binary search solution cause time limited error?


  • 0
    D

    This is C# solution, and the code are below. I search the history post and find even o(n) code AC but my binary search code failed....What a world!

    public int SearchInsert(int[] nums, int target) {
        if(nums == null || nums.Length == 0) throw new Exception();
        if(target < nums[0]) return 0;
        if(target > nums[nums.Length -1]) return nums.Length -1;
        
        
        int left = 0, right = nums.Length -1, middle = -1;
        while(left <= right){
           middle = (right - left)/2 + left; 
           int m = nums[middle];
           if(target == m) return middle;
           if(target < m) right = middle -1;
           else left = m+1;        
        }
        
        return target > nums[middle] ? middle +1 : middle;
    }

  • 1
    D

    You did something wrong. I modified your code, where I put //here

    public class Solution {
        public int SearchInsert(int[] nums, int target) {
            if(nums == null || nums.Length == 0) throw new Exception();
            if(target < nums[0]) return 0;
            if(target > nums[nums.Length -1]) return nums.Length ; //here        
        
            int left = 0, right = nums.Length -1, middle = 0;
            while(left <= right){
               middle = (right - left)/2 + left; 
               int m = nums[middle];
               if(target == m) return middle;
               if(target < m) right = middle -1;
               else left = middle+1;   //here     
            }
        
            return target > nums[middle] ? middle +1 : middle;
        }
    }

  • 0
    D

    Thanks, you are right!!


Log in to reply
 

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