# 在频率大于或等于 n / 2 的排序数组中查找元素。

> 原文： [https://www.geeksforgeeks.org/find-element-sorted-array-whose-frequency-greater-equal-n2/](https://www.geeksforgeeks.org/find-element-sorted-array-whose-frequency-greater-equal-n2/)

给定长度为 n 的排序数组，请在数组中查找出现大于或等于 n / 2 次的数字。 假定这样的元素总是存在的。

例子：

```
Input :  2 3 3 4
Output : 3

Input :  3 4 5 5 5 
Output : 5

Input : 1 1 1 2 3
Output : 1

```

## [推荐：在继续进行解决之前，请先在 ***<u>{IDE}</u>*** 上尝试您的方法。](https://ide.geeksforgeeks.org/)

为了找到该数字，我们遍历数组，并检查数组中每个元素的频率是否大于或等于 n / 2，但它需要额外的空间，并且时间复杂度为 O（n）。
但是我们可以看到，如果在排序数组中存在大于或等于 n / 2 次的数字，则该数字必须出现在位置 n / 2，即 a [n / 2]。

## C++ 

```

// C++ code to find majority element in a 
// sorted array 
#include <iostream> 
using namespace std; 

int findMajority(int arr[], int n) 
{ 
    return arr[n / 2]; 
} 

int main() 
{ 
    int arr[] = { 1, 2, 2, 3 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    cout << findMajority(arr, n); 
    return 0; 
} 

```

## 爪哇

```

// Java code to find majority element in a 
// sorted array 
public class Test { 

    public static int findMajority(int arr[], int n) 
    { 
        return arr[n / 2]; 
    } 
    public static void main(String args[]) 
    { 
        int arr[] = { 1, 2, 2, 3 }; 
        int n = arr.length; 
        System.out.println(findMajority(arr, n)); 
    } 
} 

```

## Python 3

```

# Python 3 code to find 
# majority element in a 
# sorted array 

def findMajority(arr, n): 

    return arr[int(n / 2)] 

# Driver Code 
arr = [1, 2, 2, 3] 
n = len(arr)  
print(findMajority(arr, n)) 

# This code is contributed by Smitha. 

```

## C# 

```

// C# code to find majority element in a 
// sorted array 
using System; 

public class GFG { 

    public static int findMajority(int []arr, int n) 
    { 
        return arr[n / 2]; 
    } 

    // Driver code 
    public static void Main() 
    { 

        int []arr = { 1, 2, 2, 3 }; 
        int n = arr.Length; 

        Console.WriteLine(findMajority(arr, n)); 
    } 
} 

// This code is contributed by vt_m.  

```

## PHP

```

<?php 
// PHP code to find majority  
// element in a sorted array 

function findMajority($arr, $n) 
{ 
    return $arr[intval($n / 2)]; 
} 

    // Driver Code 
    $arr = array(1, 2, 2, 3); 
    $n = count($arr); 
    echo findMajority($arr, $n);      

// This code is contributed by Sam007 
?> 

```

Output:

```
2

```

时间复杂度：O（1）

**相关文章**：
 [未排序数组中的多数元素](https://www.geeksforgeeks.org/majority-element/)
[检查排序数组中的多数元素](https://www.geeksforgeeks.org/check-for-majority-element-in-a-sorted-array/)

本文由 **Amit Kumar** 提供。 如果您喜欢 GeeksforGeeks 并希望做出贡献，则也可以使用 [tribution.geeksforgeeks.org](http://www.contribute.geeksforgeeks.org) 撰写文章，或将您的文章邮寄至 tribution@geeksforgeeks.org。 查看您的文章出现在 GeeksforGeeks 主页上，并帮助其他 Geeks。

如果发现任何不正确的地方，或者想分享有关上述主题的更多信息，请写评论。

现在不要停下来，将您的学习提高到一个新的水平。 借助最受信任的课程，学习数据结构和算法的所有重要概念： [DSA Self Paced](https://practice.geeksforgeeks.org/courses/dsa-self-paced?utm_source=geeksforgeeks&utm_medium=article&utm_campaign=gfg_article_dsa_content_bottom) 。 以对学生友好的价格准备好行业。