旋转有序数组中查找一个数

思路:二分法思想,先找出该数存在的某段有序数组中,随意取一个下边,它的左边和右边总有一个是有序的段,而如果这个查找的数刚好在这个段中,就可以利用二分法了。

class XuanZhuanYouXuChaZhao
{
    public int Find(int[] datas,int num)
    {
        int left = 0;
        int right = datas.Length - 1;
        int mid = 0;
        while (true)
        {
            if (left > right) return -1;
            mid = (left + right) / 2;
            if (num == datas[mid]) return mid;
            if (datas[mid] > datas[left])//左边有序
            {
                if (num < datas[mid] && num >= datas[left])
                {
                    //左边二分法
                    right = mid - 1;
                    break;
                }
                else
                {
                    //在右边 继续找有序
                    left = mid + 1;
                }
            }
            else//右边有序
            {
                if (num > datas[mid] && num <= datas[right])
                {
                    //右边二分法
                    left = mid + 1;
                    break;
                }
                else
                {
                    //在左边,继续查找有序
                    right = mid - 1;
                }
            }
        }

        //二分法查找
        while (left <= right)
        {
            mid = (left + right) / 2;
            if (num == datas[mid]) return mid;
            if (num > datas[mid])//右边找
            {
                left = mid + 1;
            }
            else//左边找
            {
                right = mid - 1;
            }
        }

        return -1;
    }
}
//旋转有序数组中查找
static void TestXuanZhuanYouXuChaZhao()
{
    XuanZhuanYouXuChaZhao XZY = new XuanZhuanYouXuChaZhao();
    int[] datas = {20,50,90,2,5,9,11,18,19 };
    int[] datas2 = { 300,500,1,2,3,4,5,6,7,8,9,10,11,13,15,18,22,30,38,40,45,55,66,77,88 };
    Console.WriteLine(XZY.Find(datas, 18));//7
    Console.WriteLine(XZY.Find(datas, 20));//0
    Console.WriteLine(XZY.Find(datas2, 9));//10
    Console.WriteLine(XZY.Find(datas2, 77));//23
    Console.WriteLine(XZY.Find(datas2, 22));//16
}



首页 我的博客
粤ICP备17103704号