leetcode:Search Insert Position

leetcode:Search Insert Position

一、 題目

在一個數組中查詢一個目標數，給出的是一個有序的數組、元素個數和目標數，不過特別的是這個數組可能是旋轉(rotate)的。

例如：數組可能是 0、1、2、4、5、6

也可能是4、5、6、0、1、2

二、 分析

這個題首先我們會想到二分查找，但是仔細想想好像又不是，因為不一定是正序的，還有可能旋轉，因為rotate的原因，如果我們取一半的時候可能會出現錯誤，二分法不是不行，難度在於左右邊界的確定，所以我們要做進一步的判斷數的精確位置。假設數組是A，每次左邊緣為left，右邊緣為right，還有中間位置是mid。

分三種情況：

（1）如果target==A[mid]，那麼mid就是我們要的結果，直接返回；

（2）如果A[mid]

（3）如果A[mid]>=A[right]，那麼同樣說明從left到mid一定是有序的，同樣只需要判斷target是否在這個范圍內，相應的移動邊緣即可。

class Solution {
public:
    int search(int A[], int n, int target) {
    	if(n==0)
    		return -1;
        int left = 0;
        int right = n-1;
        int mid;
		while(left <= right) {
			mid = (left+right)/2;
			if(target==A[mid])
				return mid;
			//確定數組特征 
			if(A[mid]A[mid]&&target<=A[right])
					left = mid+1;
				else
					right = mid -1;	
			}	
			else if(target>=A[left]&&target