C# solution: binary search with the explanation


  • 0
    B

    For example:

    Always compare [mid] and [right]

    All possible pivots:
    0,1,2,4,5,6,7 4 < 7 : the right part is ordered
    1,2,4,5,6,7,0 5 > 0 : the left part is ordered
    2,4,5,6,7,0,1 6 > 1 : the left part is ordered
    4,5,6,7,0,1,2 7 > 2 : the left part is ordered
    5,6,7,0,1,2,4 0 < 4 : the right part is ordered
    6,7,0,1,2,4,5 1 < 5 : the right part is ordered
    7,0,1,2,4,5,6 2 < 6 : the right part is ordered

    public class Solution 
    {
        public int Search(int[] nums, int target) 
        {
            if (nums.Length == 0) return -1;
    
            var n = nums.Length;
    
            var left = 0;
            var right = n - 1;
    
            while(left <= right)
            {
                var mid = left + (right - left) / 2;
    
                if (nums[mid] == target) return mid;
                else if (nums[mid] <= nums[right])
                {
                    // right part is ordered
                    if (nums[mid] < target && target <= nums[right])
                    {
                        left = mid + 1;
                    }
                    else
                    {
                        right = mid - 1;
                    }
                }
                else if (nums[mid] >= nums[right])
                {
                    // left part is ordered
                    if (nums[left] <= target && target < nums[mid])
                    {
                        right = mid - 1;
                    }
                    else
                    {
                        left = mid + 1;
                    }
                }
            }
    
            return -1;
        }
    }
    

Log in to reply
 

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