元素查找

class Finder {
public:
    int findElement(vector<int> A, int n, int x) {
        int i = 0, j = n - 1, mid = 0;
        while (i <= j) {
            mid = (i + j) / 2;
            if (A[mid] == x) {
                return mid;
            } else if (A[mid] > x) {
                if (A[mid] > A[i] && x < A[i]) {
                    i = mid + 1;
                } else {
                    j = mid - 1;
                }
            } else {
                if (A[mid] < A[j] && x > A[j]) {
                    j = mid - 1;
                } else {
                    i = mid + 1;
                }
            }
        }
        return -1;
    }
};

二分查找的加强版，主题思路还是二分，再加上一些限制条件
int findElement(vector<int> A, int n, int x) {
        int i=0,j=n-1,mid;
        while(i<=j) {
            mid=(i+j)/2;
            if(A[mid]==x)
                return mid;
            if(A[mid]<x) {
            	if(A[mid]<A[i]&&x>A[j]) j=mid-1;
                else i=mid+1;
            } 
			else {
				if(A[mid]>A[i]&&x<A[i]) i=mid+1;
				else j=mid-1;
            }
        }
        return -1;
}

public int findElement(int[] A, int n, int x) {
        // write code here
        //二分查找
        //注意：利用题意中的 这是一个排过序的数组
        int left=0;
        int right=n-1;
        int mid=0;
        //由于移位了，但移位之后，中间元素的左右两边必定有一边是升序的
      
        while(left<=right) {
            mid=(left+right)/2;
            if(A[mid]==x)
                return mid;
            if(A[mid]<x) {
                //A[mid]<A[left] 说明右边是有序的，且x>A[right]说明x在mid左边
                if(A[mid]<A[left]&&x>A[right]) right=mid-1;
                else left=mid+1;
            }
            else {
                //A[mid]>A[left]说明左边是有序的，且x<A[left]，说明x在mid右边
                if(A[mid]>A[left]&&x<A[left]) left=mid+1;
                else right=mid-1;
            }
        }
        return -1;
    
    }

//画图限制条件就会一目了然，限制条件发生在：两段有序的线段，前一段全部大于后一段
//mid 和 x 分别在两个线段上
import java.util.*; public class Finder {
    public int findElement(int[] A, int n, int x) {
        if(A == null || n == 0){
            return -1;
        }
        int start = 0, end = n - 1;
        while(start <= end){
            int mid = start + (end - start) / 2;
            if(A[mid] == x){
                return mid;
            }else if(A[mid] < x){
                if(A[mid] < A[start] && x > A[end]){
                    end = mid - 1;
                }else{
                    start = mid + 1;
                }
            }else{//A[mid] > x
                if(A[mid] > A[start] && x < A[start]){
                    start = mid + 1;
                }else{
                    end = mid - 1;
                }
            }
        }
        return -1;
    }
}

# -*- coding:utf-8 -*-

class Finder:
    def findElement(self, A, n, x):
        # write code here
        return A.index(x)

/*
思路:
二分法解答。
找到数组中间的数mid，确定目标数x在该数的哪一边。
x大于mid，分两种情况。 如果数组开头数大于mid且小于等于x，x在左侧; 否则在右侧.
x小于mid，分两种情况。 如果数组开头数小于等于mid且大于x，x在右侧; 否则在左侧.

根本思想:找到mid和x之前的一段数，将这些数从原序左移到开头，则mid和x必将不在同一侧!
	x>mid:
0 1 2 3 4
[6, 1, 2, 3, 4]
mid = 2, x = 6
[1, 2, 3, 4, 6] mid = 2, x = 6时，数组开头数是>2 <= 6之间可确保6在2左侧
[2, 3, 4, 6, 1]
[3, 4, 6, 1, 2]
[4, 6, 1, 2, 3]
[6, 1, 2, 3, 4]

x<mid:
0 1 2 3 4
[2, 3, 4, 6, 1]
mid = 4, x = 1
[1, 2, 3, 4, 6] mid = 4, x = 1时，数组开头数是>1 <= 4之间可确保1在4右侧。
[2, 3, 4, 6, 1]
[3, 4, 6, 1, 2]
[4, 6, 1, 2, 3]
[6, 1, 2, 3, 4]
*/
class Finder {
public:
	int findElement(vector<int> A, int n, int x) {
		// write code here
		return find(A, 0, n - 1, x);
	}
	int find(vector<int> A, int start, int end, int x)
	{
		int ret;
		if (start > end) return -1;		//没有找到返回-1
		int mid = start + (end - start) / 2;
		if (A[mid] == x) ret = mid;
		if (x > A[mid])
		{
			if (A[start]>A[mid]&&A[start]<=x) ret=find(A, start, mid-1, x);
			else ret=find(A, mid+1, end, x);
		}
		if (x < A[mid])
		{
			if (A[start]<=A[mid]&&A[start]>x) ret=find(A, mid+1, end, x);
			else ret=find(A, start, mid-1, x);
		}

		return ret;
	}
};

public int findElement(int[] A, int n, int x) {
		if(A == null || n < 0)
			return -1;
		int start = startFind(A, 0, n - 1);
		if(x > A[n - 1])
			return binFind(A, 0, start - 1, x);
		else
			return binFind(A, start, n - 1, x);
	}

	public int binFind(int[] A, int start, int end,int x) {  //二分法
                if(A == null || start > end)
			return -1;
		int mid = (start + end) / 2;
		if(A[mid] == x)
			return mid;
		else if(A[mid] > x)
			return binFind(A, start, mid - 1, x);
		else
			return binFind(A, mid + 1, end, x);
	}
	
	public int startFind(int[] A, int start, int end) {  //二分法找头元素的位置  
    	if(A == null || start > end)
                      return -1;
               int mid = (start + end) / 2;
		if(A[mid] > A[mid+1])
			return (mid+1);
		else{
			if(A[mid] < A[end])
				return startFind(A, start, mid);
			else
				return startFind(A, mid, end);
		}
	}

class Finder {
public:
    int findElement(vector<int> A, int n, int x) {
        int l=0,r=n-1,m=l;         while(l<=r){             m = (l+r)>>1;             if(A[m] == x)                 return m;             else if(A[m]<x){                 if(A[l]>A[m] && x>A[r])                     r = m-1;                 else                     l = m+1;             }else{                 if(A[r]<A[m] && x<A[l])                     l = m+1;                 else                     r = m-1;             }         }         return -1;
    }
};

还是二分查找没变。变得是每次调整end 和start 的时候，需要把可能的乱序情况考虑进去。
当 A[mid] < x 的时候， 乱序是X 在数组的前半段,因为数组中大的都被移到的前面。
那么一定需要条件 X > A[end] 并且 A[mid] < A[Start]。
当A[mid] > x 的时候， 乱序是X 在数组后面。也就是 小数在数组的最后面。
那么一定有 A[mid] > A[start] && x < A[start]
其他的情况就是正常的二分查找。

class Finder {
public:
    int findElement(vector<int> A, int n, int x) {
        // write code here
        int start = 0;
        int end = n - 1;
        int mid = 0;
        while (start <= end) {
            mid = (start + end) / 2; 
            if (A[mid] == x) return mid;
            if (A[mid] < x) {
                if (x > A[end] && A[mid] < A[start]) end = mid - 1;
                else start = mid + 1;
            } else {
                if (A[mid] > A[start] && x < A[start]) start = mid + 1;
                else end = mid - 1;
            }
        }
        return -1;
    }
};

class Finder {
public:
    int binarySearch(vector<int>& A, int left, int right,int x)
    {
        while (left < right)
        {
            int mid = (left + right) >> 1;
            if (A[mid] == x) return mid;
            else if (A[mid] < x) left = mid + 1;
            else right = mid - 1;
        }

        return left;
    }
    int findElement(vector<int> A, int n, int x)
    {
        int left = 0, right = n - 1;
        while (left < right)
        {
            if (A[left] < A[right]) return binarySearch(A, left, right,x);
            if (A[left] == x) return left;
            if (A[right] == x) return right;
            int mid = (left + right) >> 1;
            if (A[mid] == x) return mid;
            if (A[mid] > A[left])
            {
                if (x < A[mid] && x > A[left]) right = mid - 1;
                else left = mid + 1;
            }
            else
            {
                if (x > A[mid] && x < A[right]) left = mid + 1;
                else right = mid - 1;
            }
        }

        return left;
    }
};

public int findElement(int[] A, int n, int x) {
        for (int l = 0, r = n - 1, m = (l + r) / 2; l <= r; m = (l + r) / 2) {
            if (x > A[m]) {
                if (A[m] < A[r] && x > A[r])
                    r = m - 1;
                else
                    l = m + 1;
            } else if (x < A[m]) {
                if (A[l] < A[m] && x < A[l])
                    l = m + 1;
                else
                    r = m - 1;
            } else {
                return m;
            }
        }
        return -1;
    }
------------------------------------------
public int findElement(int[] A, int n, int x) {
       return findElement(A, 0, n - 1, x);
   }
 
   public int findElement(int[] A, int l, int r, int x) { //确定区间
       if (l > r) {
           return -1;
       }
       int m = (l + r) / 2;
       if (A[m] < A[r]) {  //右部处于单调
           if (A[m] <= x && x <= A[r]) {
               return binerySearch(A, m, r, x);
           }
           return findElement(A, l, m - 1, x); //左边找
       } else { //左部处于单调
           if (A[l] <= x && x <= A[m]) {
               return binerySearch(A, l, m, x);
           }
           return findElement(A, m + 1, r, x); //右边找
       }
   }
 
   public int binerySearch(int[] A, int l, int r, final int x) { //二分查找
       for (int m = (l + r) / 2; l <= r; m = (l + r) / 2) {
           if (x > A[m]) {
               l = m + 1;
           } else if (x < A[m]) {
               r = m - 1;
           } else {
               return m;
           }
       }
       return -1;
   }

变版本二分而已，还算比较简单的题目。搞清楚是前半部分按顺序排列还是后半部分按顺序排列就ok
import java.util.*;

public class Finder {
    public int findElement(int[] A, int n, int x) {
        int start = 0;
        int end = n - 1;
        int m;        
        while(start <= end){
            m = (start + end) / 2;
            if(A[m] == x)
                return m;
            else if(A[end] > A[m]){ // 后半部分按顺序排列
                if(A[end] < x || A[m] > x) // 在前半部分
                    end = m - 1;
                else //A[m] < x // 一定在后半部分
  		    start = m + 1;                
            } 
            else if(A[end] < A[m]){ // 前半部分按顺序排列
                if(A[m] < x || A[start] > x)
                    start = m + 1;
                else
                    end = m - 1;                
            }                         
        }
        return -1;
    }
}

    public int findElement(int[] A, int n, int x)
    {
        int temp = 0;
        for (int i = A.Length - 2; i > -1; i--)
        {
            if (A[i] > A[i + 1])
                temp = i + 1;
        
        }
        if (x > A.Length - temp)
            return x - A.Length + temp-1;
        else 
            return temp + x-1;
    }

// 由于元素互异, 感觉利用一点技巧就能ok...
public int findElement(int[] A, int n, int x) {
    // write code here
    return x >= A[0] ? (x - A[0]) : (n - A[0] + x) ;
}

import java.util.*;
/*
思路：既然是向左进行了移位，那判断的时候就得先判断一下左右两边的值的大小和所求值大小的关系，然后再判断
遇到的问题：那几个情况不能都用if连接，因为他们中有且只有一个发生，需要用if、else if连接，这地方错了几次- -气哭
*/
public class Finder {
    public int findElement(int[] A, int n, int x) {
        int start =0;
        int end =n-1;
        if(x==A[n-1]) return n-1;
        if(x>A[n-1]){
           while(start<=end){
            	int mid =(start+end)/2;
                if(x==A[mid]) return mid;
            	if(x>A[mid]&&A[mid]>=A[0]){
                    start=mid+1;
                }//mid已经在移过来的那一段了
               	else if(x>A[mid]&&A[mid]<=A[0]){
                    end=mid-1;
                }//mid还在没移过来的部分
                else if(x<A[mid]){
                    end =mid-1;
                }//mid一定移过来了
       			
           } 
        }//如果x大于最右边的值，代表在左移的那一段里面
        else{
            while(start<=end){
            	int mid =(start+end)/2;
                if(x==A[mid]) return mid;
            	if(x<A[mid]&&A[mid]>=A[0]){
                    start =mid+1;
                }//mid已经是移过来的这部分了
                else if(x<A[mid]&&A[mid]<=A[0]){
                    end =mid-1;
                }//mid还没有移过来
                else if(x>A[mid]){
                    start =mid+1;
                }//看右半部分就好
                
        	}
        }//如果x小于最右边的值，代表在没移过来的那一段里面
        return -1;
        
        
    }
}
运行时间：53ms
占用内存：9476k