首页 > 试题广场 >

元素查找

[编程题]元素查找

热度指数：8823 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定一个数组A及其大小n，同时给定需要查找的元素值x，已知数组A是由一个排过序的数组向左移位了一定长度得到的，请返回x在现数组的位置(位置从零开始)。保证数组中元素互异。

测试样例：

[6,1,2,3,4,5],6,6

返回：0

算法知识视频讲解

木然猫猫

二分法的思想虽然简单，但代码不容易写对。

对本题进行分析，设左右位置为i, j，中间位置为mid

先考虑x<A[mid]的情况，分四种情况，每种情况以及对i, j的重新赋值如下：

注意第二张图的i=mid+1的情况，总结一下它的特点是：A[mid] > A[j] && x < A[i] （注意要和其它情况区分）

另外，上面的A[mid] > A[j] && x < A[i]里，x 必须是<A[i]而不是<A[j]，因为要考虑到x和A[j]相等的情况。而A[mid] > A[j]换成A[mid] > A[i]也没关系。

x>A[mid]同理。x == A[mid]直接返回mid

代码：

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;
    }
};

发表于 2018-12-28 19:15:08 回复(0)

更多回答

L0L

二分查找的加强版，主题思路还是二分，再加上一些限制条件
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;
}

发表于 2015-10-12 17:26:06 回复(3)

philian

我习惯画个曲线图……比较直观些

假设左移后的各元素大小如上面的曲线图所示，横轴（没画）从左至右依次为下标，数轴是各元素的数值，由于左移，所以在其中某个节点处有数值的单调性突变，在这个点之前和之后都是单增的，不妨叫它【突变点】（其实是数组的头元素啦）
采用二分法，得到中分点（图仅示意，不要在意它是不是真的画在中间），这里用绿线标出，那么待查找元素x和中分点的数值大小就有三种可能：=，>，<。相等的情况不说了，>和<在图中用紫线标出
接下来根据中分点在突变点左侧or右侧可以划分出两种情况
1、情况一：中分点在突变点左侧

紫线与曲线相交的横坐标即为待查找元素可能的下标，可以看出如果x>A[mid]，那x的下标一定在mid右侧，如果x<A[mid]，那x需要跟A[lo]或A[hi-1]比较确定接下来查找的区间
2、情况二：中分点在突变点右侧：

可以看出在这种情况下，如果x<A[mid]，x的下标一定在mid左侧，如果x>A[mid]，x需要跟A[lo]或A[hi-1]比较确定接下来查找的区间

class Finder {
public:
	int findElement(vector<int> A, int n, int x) {
		// write code here
		if (n<1)return -1;
		int lo = 0, hi = n;
		while (lo<hi){
			int mid = (lo + hi) >> 1;
			if (A[mid] == x)return mid;
			if (A[mid]<=A[hi - 1]){//mid和hi-1可能重合
				if (A[mid]<x){
					if (A[hi - 1]>=x){
						lo = mid + 1;
					}
					else{
						hi = mid;
					}
				}
				else{
					hi = mid;
				}
			}
			else{
				if (A[mid]>x){
					if (A[hi - 1]>=x){
						lo = mid + 1;
					}
					else{
						hi = mid;
					}
				}
				else{
					lo = mid + 1;
				}
			}
		}
		return -1;
	}
};

发表于 2016-11-10 22:21:03 回复(0)

骑士feif

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;
    
    }

发表于 2016-08-29 08:44:57 回复(2)

BrainerGao

//画图限制条件就会一目了然，限制条件发生在：两段有序的线段，前一段全部大于后一段
//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;
    }
}

发表于 2017-05-21 23:26:40 回复(0)

Python

华科平凡

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

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

发表于 2017-10-07 14:19:17 回复(0)

C/C++

羽落长安

/*
思路:
二分法解答。
找到数组中间的数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;
	}
};

发表于 2017-02-20 17:40:40 回复(0)

苏幕烟雨

二分法的使用，先找头元素的位置，再找最终位置

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);
		}
	}

最终时间复杂度为O(logn)

发表于 2015-09-03 17:12:53 回复(0)

C/C++

nbgao

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;
    }
};

发表于 2019-03-01 02:12:34 回复(0)

Ga_li_dun_farming_guy

还是二分查找没变。变得是每次调整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;
    }
};

发表于 2019-01-16 22:19:11 回复(0)

Cavs

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;
    }
};

发表于 2017-06-29 17:22:25 回复(0)

Aurora1

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;
   }

编辑于 2017-01-19 14:13:35 回复(0)

后劲好大

变版本二分而已，还算比较简单的题目。搞清楚是前半部分按顺序排列还是后半部分按顺序排列就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;
    }
}

发表于 2016-12-23 14:11:59 回复(0)

林家花美男

纯粹瞎写

class Finder {

public:

int findElement(vector<int> A, int n, int x) {

// write code here

int begin = 0, end = n-1;

return find(A,begin,end,x);

}

int find(vector<int> &A , int begin , int end ,int x){

int mid = (begin +end)/2;

if(A[mid]==x )

return mid;

if(A[begin]<A[mid]){

if(A[begin]<=x&&A[mid]>=x)

return find(A,begin,mid,x);

else

return find(A,mid,end,x);

}

else{

if(A[mid]<=x&&A[end]>=x)

return find(A,mid,end,x);

else

return find(A,begin,mid,x);

}

};

发表于 2016-05-20 13:20:58 回复(0)

战狼-1996

    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;
    }

返回的是位置，从后往前遍历出左移的个数，再计算即可

发表于 2016-03-18 19:36:23 回复(1)

yaknow

int findElement(vector<int> A, int n, int x)

{

// write code here

vector<vector<int> > vs;

for(int i=0;i<n;i++)//统计数组中的元素以及对应的位置

{

vector<int> v;

v.push_back(A[i]);

v.push_back(i);

vs.push_back(v);

}

int pos;

for(int i=0;i<n;i++)

{

if(vs[i][0]==x) //找到元素，返回其对应的位置

{

pos=vs[i][1];

break;

}

return pos;

}

发表于 2016-03-16 16:57:38 回复(0)

冷冰冰

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

编辑于 2015-12-19 21:22:17 回复(2)

牛客672559号

最简单思考的方法（罗列出所有可能的逻辑）：

首先把数组看成还两个数组，比如561234，则看成是56 和 1234，123456也看成是123456和空。而且第一个数组的任何一个数都比第二个数组的大。

i代表指向左端，mid是中间，j是右端,x是要找的数

(1)当A[mid]<x时：

(1.1)当A[mid]>A[i]时，说明A[mid]在第一个数组上，由于A[mid]<x说明mid这个位置的数太小，又因为其在第一个数组，往左只会越来越小，所以只能往右，即i=mid+1。

（1.2）当A[mid]<A[i]时，说明A[mid]在第二个数组上，此时如果temp<=A[j] 则i=mid+1;否则j=mid-1.

（2）当A[mid]>x时：

（2.1）当A[mid]>A[i]时，如果A[i]<=x 则j=mid-1;否则i=mid+1;

（2.2）当A[mid]<A[i]时，j=mid-1;

（以上逻辑画个图，找几个实例很容易推断出全部逻辑，然后照这些逻辑写if和else语句就可以了，应该还可以把这些再总结优化下，会少掉很多if和else，以下我的就没优化了，直接if和else放上去，比较好理解）

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])

i=mid+1;

else {

if(x<=A[j])

i=mid+1;

else j=mid-1;

}

} else {

if(A[mid]>A[i]) {

if(A[i]<=x)

j=mid-1;

else i=mid+1;

} else {

j=mid-1;

}

return -1;

}

发表于 2015-10-03 01:19:46 回复(0)

scut_huajian

写的不够简洁，其实就是多了一重判断A【mid】与A【high】的关系来决策（或者判断A【mid】与A【low】的关系也可以的），跟二分查找几乎没差别。

int findElement(vector<int> A, int n, int x) {

// write code here

int low=0;

int high=n-1;

int mid;

while(low<=high){

mid=low+((high-low)>>1);

if(x==A[mid])

return mid;

if(x>A[mid]){

if(A[low]>A[high]&&A[mid]<=A[high]){

if(x>=A[high])

high=mid-1;

else

low=mid+1;

}

else if(A[low]>A[high]&&A[mid]>A[high])

low=mid+1;

else

low=mid+1;

}

else if(x<A[mid]){

if(A[low]>A[high]&&A[mid]<=A[high])

high=mid-1;

else if(A[low]>A[high])

{

if(x>=A[low])

high=mid-1;

else

low=mid+1;

}

else

high=mid-1;

}

return -1;

}

发表于 2015-08-14 17:32:48 回复(0)

阿狸不是猫

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

发表于 2017-06-30 14:19:39 回复(0)