二分查找的改进

• 本题的调试有点问题。。

一、暴力『不是最优』

class Solution {
public:
    /**
     * 
     * @param A int整型一维数组 
     * @param n int A数组长度
     * @param target int整型 
     * @return int整型
     */
    int search(int* A, int n, int target) {
        // write code here
        int loop=n;
        while( loop-- )
        {
            if( A[loop]==target )
            {
                return loop;
            }
        }

        return -1;

    }
};

二、改进的『二分查找』

参考牛油lzx071021

//不要被“旋转”而迷惑，“有序”并不是二分查找的核心
    // 二分查找的核心是"通过界桩快速决定查找方向，大幅缩短查找空间"
    // 只要能快速确定界桩，就能使用二分查找
    // 充分利用有序数组能够快速获取边界值的特性
    // 利用这一特性可以快速确定目标值应处的区间

class Solution {
public:
    /**
     * 
     * @param A int整型一维数组 
     * @param n int A数组长度
     * @param target int整型 
     * @return int整型
     */
    int search(int* A, int n, int target) {
        // write code here
        int Left=0,Right=n-1,mid;

        while( Left<=Right )
        {
            mid= Left + (Right-Left)/2;

            if( A[mid]==target )
            {
                return mid;
            }

            //左边的有序区间
            if( A[mid]>=A[Left] )
            {
                if( A[Left]<=target && target<A[mid])
                {
                    Right=mid-1;
                }
                else 
                {
                    Left=mid+1;
                }
            }
            else 
            {
                if( A[mid]<target && target<=A[Right] )
                {
                    Left=mid+1;
                }
                else 
                {
                    Right=mid-1;
                }

            }


        }

        //没有找到的话
        return -1;
    }
};