数组排序查找已排序的旋转后的数组中的数（Search in Rotated Sorted Array）

本文是一篇关于数组排序的帖子

标题如下：

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

分析：此题最单简的方法就是一个个较比，复杂度O(N)，但这样就没有用利分段排序这个件条。

我的设法是先用二分搜索将数组分红两个已排序的数组，再在这两个数组上查找，这样算法复杂度为O(lgN)+max（O(lgM)+O(lg(N-M))），其中0<M<N

码代如下：

每日一道理
一个安静的夜晚，我独自一人，有些空虚，有些凄凉。坐在星空下，抬头仰望美丽天空，感觉真实却由虚幻，闪闪烁烁，似乎看来还有些跳动。美的一切总在瞬间，如同“海市蜃楼”般，也只是刹那间的一闪而过，当天空变得明亮，而这星星也早已一同退去……

int findmax(int A[], int n){
        int max=A[0];
        int i=0,j=n-1,m=i+(j-i)/2+1;
        while(i!=j)
        {
           if(max<A[m])
           {
               i=m;
               max=A[m];
           }
           if(max>A[m])j=m-1;
           m=i+(j-i)/2+1;
        }
        return i;
    }
    int binarysearch(int A[], int n, int target)
    {
        int i=0,j=n-1,m=i+(j-i)/2;
        while(i<=j)
        {
           if(target==A[m])break;
           if(target<A[m])j=m-1;
           if(target>A[m])i=m+1;
           m=i+(j-i)/2;
        }
        if(i<=j)return m;
        return -1;
    }
    int search(int A[], int n, int target) {
        if(n<=0)return -1;
        int position=findmax(A,n);
        int result=binarysearch(A, position+1, target);
        if(result!=-1)return result;
        if(n>position+1)
        {
            result=binarysearch(A+position+1, n-position-1, target);
            if(result!=-1)return result+position+1;
        }
        return -1;
    }

文章结束给大家分享下程序员的一些笑话语录：系统程序员
　　1、头皮经常发麻，在看见一个蓝色屏幕的时候比较明显，在屏幕上什幺都看不见的时候尤其明显；
　　2、乘电梯的时候总担心死机，并且在墙上找reset键；
　　3、指甲特别长，因为按F7到F12比较省力；
　　4、只要手里有东西，就不停地按，以为是Alt-F、S；
　　5、机箱从来不上盖子，以便判断硬盘是否在转；
　　6、经常莫名其妙地跟踪别人，手里不停按F10；
　　7、所有的接口都插上了硬盘，因此觉得26个字母不够；
　　8、一有空就念叨“下辈子不做程序员了”；
　　9、总是觉得9号以后是a号；
　　10、不怕病毒，但是很害怕自己的程序；