0ms C solution using bin search


  • 0
    O
    int binSearch(int * nums, int start, int end, int target){
        while (1) {
            if (start + 1 == end) {
                if (nums[start] == target) {
                    return start;
                }
                if (nums[end] == target) {
                    return end;
                }
                return -1;
            }
            
            int pos = (start + end)/2;
            
            if (nums[pos] == target) {
                return pos;
            }
            else if(nums[pos] > target){
                end = pos;
            }
            else {
                start = pos;
            }
        }
        return -1;
    }
    
    int search(int* nums, int numsSize, int target) {
        
        if (nums[numsSize-1] > nums[0]) {
            return binSearch(nums, 0, numsSize-1, target);
        }
        
        if (numsSize == 1) {
            if (nums[0] == target) {
                return 0;
            }
            return -1;
        }
               
        int start = 0, end = numsSize-1;
    
        while (1) {
            if (start + 1 == end) {
                if (nums[start] == target) {
                    return start;
                }
                if (nums[end] == target) {
                    return end;
                }
                return -1;
            }
            
            int pos = (start + end)/2;
            
            if (nums[start] == target) {
                return start;
            }
            
            if (nums[pos] == target) {
                return pos;
            }
            
            if (nums[start] < target) {
                //upper
                if (nums[pos] > target) {
                    return binSearch(nums, start, pos, target);
                }
                else {
    //                start = pos;
    //                continue;
                    if (nums[pos] < nums[start]) {
                        end = pos;
                        continue;
                    }else{
                        start = pos;
                        continue;
                    }
                }
            }
            else {
                //for lower
                if (nums[pos] < target) {
                    return binSearch(nums, pos, end, target);
                    
                }
                else {
                    if (nums[pos] < nums[start]) {
                        end = pos;
                        continue;
                    }else{
                        start = pos;
                        continue;
                    }
                   
                }
            }
            
            
        }
        
        return -1;
    }
    

Log in to reply
 

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