Short C# Solution Time O(log(n)) SpaceO(1) 175ms with Step Explanations


  • -1
    L
    //The idea is to find out the rotating point (index newStart)
    //then use newStart as starting point
    //and newStart + nums.Length - 1 as ending point to do log(n) search.
        public class Solution {
            public int Search(int[] nums, int target) {
                int begin = 0, end = nums.Length - 1;
                int len = nums.Length;
                int newStart;
    
                //1. Loop to find out rotating point newStart
                while (begin < end)
                {
                    if (nums[(begin + end) / 2] < nums[len - 1])
                        end = (begin + end) / 2;
                    else if (nums[(begin + end) / 2] > nums[len - 1])
                        begin = (begin + end + 1) / 2;
                }
                newStart = nums[begin] < nums[len - 1] ? begin : end;
    
                //2. Loop to find out target value from newStart
                //    if the index is larger than nums.Length then subtract nums.Length to get the real index
                begin = newStart;
                end = newStart + len - 1;
                while (begin < end)
                {
                    int mid = (begin + end) / 2 > len - 1 ? ((begin + end) / 2 - len) : (begin + end) / 2;
                    if (nums[mid] > target)
                        end = (begin + end) / 2;
                    else if (nums[mid] < target)
                        begin = (begin + end + 1) / 2;
                    else
                        return mid;
                }
    
                if (end > len - 1) end -= len;
                return nums[end] == target ? end : -1;
        
            }
        }

Log in to reply
 

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