溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
把一個有序數組進行旋轉，對于已知旋轉后的數組，找出這個數組中的最小值。
這個問題看起來比較簡單，只要遍歷一遍數組就能找到最小值，但如果題目中對時間復雜度有要求，那么這個時候就要考慮用其他的方法。
可以想到一種方法，二分查找法，每一次二分查找一定會有一邊的數字是連續且是遞增的，這個時候我們要找的最小值一定在另一邊，我們又把查找的范圍放在另一邊，以此下去，最終找到最小值，代碼如下：
int find(int a[], int size)
{
int left = 0;
int right = size - 1;
while (left <= right)
{
int mid = (left &right) + (left^right) / 2;
if (a[mid] <= a[left] && a[mid] <= a[right])
{
return a[mid];
}
else if (a[mid] < a[left])
{
right = mid - 1;
}
else if (a[mid] > a[right])
{
left = mid + 1;
}
}
return -1;
}
int main()
{
int a[] = { 3, 4, 5, 1, 2 };
int ret = find(a, 5);
printf("%d", ret);
system("pause");
return 0;
}
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
