題目

假設(shè)按照升序排序的數(shù)組在預(yù)先未知的某個(gè)點(diǎn)上進(jìn)行了旋轉(zhuǎn)。
( 例如，數(shù)組 [0,1,2,4,5,6,7] 可能變?yōu)?[4,5,6,7,0,1,2] )。
搜索一個(gè)給定的目標(biāo)值，如果數(shù)組中存在這個(gè)目標(biāo)值，則返回它的索引，否則返回 -1 。
你可以假設(shè)數(shù)組中不存在重復(fù)的元素。
你的算法時(shí)間復(fù)雜度必須是 O(log n) 級(jí)別。

題目分析

對(duì)于旋轉(zhuǎn)排序數(shù)組會(huì)出現(xiàn)兩種情況，以 [0,1,2,4,5,6,7] 舉例

• [6,7,0,1,2,4,5]，nums[start] > nums[mid]，后半段有序。如果 nums[mid] < target <=nums[end]，則在后半段找。否則，在前半段找。
• [1,2,4,5,6,7,0]，nums[start] < nums[mid]，前半段有序。如果 nums[start] <= target < num[mid]，則在前半段找。否則，后在后半段找。

public static int Method(int[] nums, int target)
        {
            var start = 0;
            var end = nums.Length - 1;
            while (start <= end)
            {
                var mid = start + (end - start) / 2;
                if (target == nums[mid])
                {
                    return mid;
                }

                if (nums[start] <= nums[mid]) // 前半段有序
                {
                    if (target >= nums[start] && target < nums[mid])
                    {
                        end = mid - 1;
                    }
                    else
                    {
                        start = mid + 1;
                    }
                }
                else // 后半段有序
                {
                    if (target > nums[mid] && target <= nums[end])
                    {
                        start = mid + 1;
                    }
                    else
                    {
                        end = mid - 1;
                    }
                }
            }

            return -1;
        }

注意 while (start <= end) 中小于等于，只剩兩個(gè)數(shù)時(shí)，進(jìn)行匹配。
以及 if (target >= nums[start] && target < nums[mid]) 中 大于等于；if (target > nums[mid] && target <= nums[end]) 中 小于等于。