溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
using namespace std;
/**
* 從有序遞增旋轉數組45679123 中找到數字6的位置
* 數組遞增 但有旋轉
* 二分查找思想
* 時間復雜度小于O(N)
* {7,8,9,10,1,2,3,4,5,6}
*************/
int find_revolve_array(const int arr[], int len, int value)
{
if (NULL == arr || len < 0)
{
throw exception("Invalid input");
return 0;
}
int left = 0;
int right = len - 1;
int mid = -1;
while (left <= right)
{
mid = (left - right) / 2 + right; // 不要用 left / 2 + right / 2 因為(5 + 7)/2 = 6 而 (5/2 + 7/2) = 5
// 9/2 + 9/2 = 8 遇不見最后一個數 可能死循環
if (arr[mid] == value)
{
return mid;
}
else if (value < arr[mid])
{
if (value >= arr[left]) // 在左邊
{
right = mid -1;
}
else // 在右邊
{
left = mid + 1;
}
}
else
{
if (value <= arr[right])
{
left = mid + 1;
}
else
{
right = mid - 1;
}
}
}
return -1;
}
void test()
{
int arr[] = {7,8,9,10,1,2,3,4,5,6};
int index = find_revolve_array(arr, 10, 7);
}
int main()
{
test();
return 0;
}
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
