Dada una array ordenada en la que todos los elementos aparecen dos veces (uno después de uno) y un elemento aparece solo una vez. Encuentre ese elemento en complejidad O (log n).
Ejemplo:
C++
// C++ program to find the element that
// appears only once
#include <bits/stdc++.h>
using namespace std;
// A Linear Search based function to find
// the element that appears only once
void search(int arr[], int n)
{
int ans = -1;
for (int i = 0; i < n; i += 2) {
if (arr[i] != arr[i + 1]) {
ans = arr[i];
break;
}
}
if (arr[n - 2] != arr[n - 1])
ans = arr[n-1];
// ans = -1 if no such element is present.
cout << "The required element is " << ans << "\n";
}
// Driver code
int main()
{
int arr[] = { 1, 1, 2, 4, 4, 5, 5, 6, 6 };
int len = sizeof(arr) / sizeof(arr[0]);
search(arr, len);
return 0;
}
// This code is contributed by yashbeersingh42
Java
// Java program to find the element that
// appears only once
import java.io.*;
class GFG {
// A Linear Search based function to find
// the element that appears only once
static void search(int arr[], int n)
{
int ans = -1;
for (int i = 0; i < n; i += 2) {
if (arr[i] != arr[i + 1]) {
ans = arr[i];
break;
}
}
if (arr[n - 2] != arr[n - 1])
ans = arr[n-1];
// ans = -1 if no such element is present.
System.out.println("The required element is "
+ ans);
}
public static void main(String[] args)
{
int arr[] = { 1, 1, 2, 4, 4, 5, 5, 6, 6 };
int len = arr.length;
search(arr, len);
}
}
Python3
# Python3 program to find the element that
# appears only once
# A Linear Search based function to find
# the element that appears only once
def search(arr, n):
ans = -1
for i in range(0, n, 2):
if (arr[i] != arr[i + 1]):
ans = arr[i]
break
if(arr[n-2] != arr[n-1]):
ans = arr[n-1]
# ans = -1 if no such element is present.
print("The required element is", ans)
# Driver code
arr = [1, 1, 2, 4, 4, 5, 5, 6, 6]
Len = len(arr)
search(arr, Len)
# This code is contributed by divyesh072019
C#
// C# program to find the element that
// appears only once
using System;
class GFG {
// A Linear Search based function to find
// the element that appears only once
static void search(int[] arr, int n)
{
int ans = -1;
for (int i = 0; i < n; i += 2) {
if (arr[i] != arr[i + 1]) {
ans = arr[i];
break;
}
}
if (arr[n - 2] != arr[n - 1])
ans = arr[n-1];
// ans = -1 if no such element is present.
Console.Write("The required element is "
+ ans);
}
public static void Main(String[] args)
{
int[] arr = { 1, 1, 2, 4, 4, 5, 5, 6, 6 };
int len = arr.Length;
search(arr, len);
}
}
// This code is contributed by shivanisinghss2110
Javascript
<script>
// JavaScript program to find the element that
// appears only once
// A Linear Search based function to find
// the element that appears only once
function search(arr, n)
{
let ans = -1;
for (let i = 0; i < n; i += 2) {
if (arr[i] != arr[i + 1]) {
ans = arr[i];
break;
}
}
if (arr[n - 2] != arr[n - 1])
ans = arr[n-1];
// ans = -1 if no such element is present.
document.write("The required element is " + ans + "<br>");
}
// Driver code
let arr = [ 1, 1, 2, 4, 4, 5, 5, 6, 6 ];
let len = arr.length;
search(arr, len);
// This code is contributed by Surbhi Tyagi
</script>
C++
// C++ program to find the element that
// appears only once
#include <bits/stdc++.h>
using namespace std;
// A XOR based function to find
// the element that appears only once
void search(int arr[], int n)
{
int XOR = 0;
for (int i = 0; i < n; i++) {
XOR = XOR ^ arr[i];
}
cout << "The required element is " << XOR << "\n";
}
// Driver code
int main()
{
int arr[] = { 1, 1, 2, 4, 4, 5, 5, 6, 6 };
int len = sizeof(arr) / sizeof(arr[0]);
search(arr, len);
return 0;
}
// This code is contributed by yashbeersingh42
Java
// Java program to find the element that
// appears only once
import java.io.*;
class GFG {
// A XOR based function to find
// the element that appears only once
static void search(int arr[], int n)
{
int XOR = 0;
for (int i = 0; i < n; i++) {
XOR = XOR ^ arr[i];
}
System.out.println("The required element is "
+ XOR);
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 1, 1, 2, 4, 4, 5, 5, 6, 6 };
int len = arr.length;
search(arr, len);
}
}
// This code is contributed by yashbeersingh42
Python3
# Python3 program to find the element that
# appears only once
# A XOR based function to find
# the element that appears only once
def search(arr, n) :
XOR = 0
for i in range(n) :
XOR = XOR ^ arr[i]
print("The required element is", XOR)
# Driver code
arr = [ 1, 1, 2, 4, 4, 5, 5, 6, 6 ]
Len = len(arr)
search(arr, Len)
# This code is contributed by divyesh072019
C#
// C# program to find the element that
// appears only once
using System;
class GFG{
// A XOR based function to find
// the element that appears only once
static void search(int []arr, int n)
{
int XOR = 0;
for(int i = 0; i < n; i++)
{
XOR = XOR ^ arr[i];
}
Console.Write("The required element is " + XOR);
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 1, 1, 2, 4, 4, 5, 5, 6, 6 };
int len = arr.Length;
search(arr, len);
}
}
// This code is contributed by shivanisinghss2110
Javascript
<script>
// JavaScript program to find the element that
// appears only once
// A XOR based function to find
// the element that appears only once
function search(arr, n)
{
let XOR = 0;
for (let i = 0; i < n; i++) {
XOR = XOR ^ arr[i];
}
document.write("The required element is " + XOR + "<br>");
}
// Driver code
let arr = [ 1, 1, 2, 4, 4, 5, 5, 6, 6 ];
let len = arr.length;
search(arr, len);
// This code is contributed by Surbhi Tyagi.
</script>
C++
// C++ program to find the element that
// appears only once
#include <iostream>
using namespace std;
// A Binary Search based function to find
// the element that appears only once
void search(int arr[], int low, int high)
{
// Base cases
if (low > high)
return;
if (low == high) {
cout << "The required element is " << arr[low];
return;
}
// Find the middle point
int mid = (low + high) / 2;
// If mid is even and element next to mid is
// same as mid, then output element lies on
// right side, else on left side
if (mid % 2 == 0) {
if (arr[mid] == arr[mid + 1])
search(arr, mid + 2, high);
else
search(arr, low, mid);
}
// If mid is odd
else {
if (arr[mid] == arr[mid - 1])
search(arr, mid + 1, high);
else
search(arr, low, mid - 1);
}
}
// Driver code
int main()
{
int arr[] = { 1, 1, 2, 4, 4, 5, 5, 6, 6 };
int len = sizeof(arr) / sizeof(arr[0]);
search(arr, 0, len - 1);
return 0;
}
// This code is contributed by ShubhamCoder
C
// C program to find the element that appears only once
#include <stdio.h>
// A Binary Search based function to find the element
// that appears only once
void search(int* arr, int low, int high)
{
// Base cases
if (low > high)
return;
if (low == high) {
printf("The required element is %d ", arr[low]);
return;
}
// Find the middle point
int mid = (low + high) / 2;
// If mid is even and element next to mid is
// same as mid, then output element lies on
// right side, else on left side
if (mid % 2 == 0) {
if (arr[mid] == arr[mid + 1])
search(arr, mid + 2, high);
else
search(arr, low, mid);
}
else // If mid is odd
{
if (arr[mid] == arr[mid - 1])
search(arr, mid + 1, high);
else
search(arr, low, mid - 1);
}
}
// Driver code
int main()
{
int arr[] = { 1, 1, 2, 4, 4, 5, 5, 6, 6 };
int len = sizeof(arr) / sizeof(arr[0]);
search(arr, 0, len - 1);
return 0;
}
Java
// Java program to find the element that appears only once
public class Main {
// A Binary Search based method to find the element
// that appears only once
public static void search(int[] arr, int low, int high)
{
if (low > high)
return;
if (low == high) {
System.out.println("The required element is "
+ arr[low]);
return;
}
// Find the middle point
int mid = (low + high) / 2;
// If mid is even and element next to mid is
// same as mid, then output element lies on
// right side, else on left side
if (mid % 2 == 0) {
if (arr[mid] == arr[mid + 1])
search(arr, mid + 2, high);
else
search(arr, low, mid);
}
// If mid is odd
else if (mid % 2 == 1) {
if (arr[mid] == arr[mid - 1])
search(arr, mid + 1, high);
else
search(arr, low, mid - 1);
}
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 1, 1, 2, 4, 4, 5, 5, 6, 6 };
search(arr, 0, arr.length - 1);
}
}
// This code is contributed by Tanisha Mittal
Python
# A Binary search based function to find # the element that appears only once def search(arr, low, high): # Base cases if low > high: return None if low == high: return arr[low] # Find the middle point mid = low + (high - low)/2 # If mid is even and element next to mid is # same as mid, then output element lies on # right side, else on left side if mid % 2 == 0: if arr[mid] == arr[mid+1]: return search(arr, mid+2, high) else: return search(arr, low, mid) else: # if mid is odd if arr[mid] == arr[mid-1]: return search(arr, mid+1, high) else: return search(arr, low, mid-1) # Driver Code # Test Array arr = [1, 1, 2, 4, 4, 5, 5, 6, 6] # Function call result = search(arr, 0, len(arr)-1) if result is not None: print "The required element is %d" % result else: print "Invalid Array"
C#
// C# program to find the element
// that appears only once
using System;
class GFG {
// A Binary Search based
// method to find the element
// that appears only once
public static void search(int[] arr, int low, int high)
{
if (low > high)
return;
if (low == high) {
Console.WriteLine("The required element is "
+ arr[low]);
return;
}
// Find the middle point
int mid = (low + high) / 2;
// If mid is even and element
// next to mid is same as mid
// then output element lies on
// right side, else on left side
if (mid % 2 == 0) {
if (arr[mid] == arr[mid + 1])
search(arr, mid + 2, high);
else
search(arr, low, mid);
}
// If mid is odd
else if (mid % 2 == 1) {
if (arr[mid] == arr[mid - 1])
search(arr, mid + 1, high);
else
search(arr, low, mid - 1);
}
}
// Driver Code
public static void Main(String[] args)
{
int[] arr = { 1, 1, 2, 4, 4, 5, 5, 6, 6 };
search(arr, 0, arr.Length - 1);
}
}
// This code is contributed by Nitin Mittal.
PHP
<?php
// PHP program to find the element
// that appears only once
// A Binary Search based function
// to find the element that
// appears only once
function search($arr, $low, $high)
{
// Base cases
if ($low > $high)
return;
if ($low==$high)
{
echo("The required element is " );
echo $arr[$low] ;
return;
}
// Find the middle point
$mid = ($low + $high) / 2;
// If mid is even and element
// next to mid is same as mid,
// then output element lies on
// right side, else on left side
if ($mid % 2 == 0)
{
if ($arr[$mid] == $arr[$mid + 1])
search($arr, $mid + 2, $high);
else
search($arr, $low, $mid);
}
// If mid is odd
else
{
if ($arr[$mid] == $arr[$mid - 1])
search($arr, $mid + 1, $high);
else
search($arr, $low, $mid - 1);
}
}
// Driver Code
$arr = array(1, 1, 2, 4, 4, 5, 5, 6, 6);
$len = sizeof($arr);
search($arr, 0, $len - 1);
// This code is contributed by nitin mittal
?>
Javascript
<script>
// Javascript implementation
// A Binary Search based function to find
// the element that appears only once
function search( arr, low, high)
{
// Base cases
if (low > high)
return;
if (low == high) {
document.write("The required element is " + arr[low]);
return;
}
// Find the middle point
var mid = Math.floor((low + high) / 2);
// If mid is even and element next to mid is
// same as mid, then output element lies on
// right side, else on left side
if (mid % 2 == 0) {
if (arr[mid] == arr[mid + 1])
search(arr, mid + 2, high);
else
search(arr, low, mid);
}
// If mid is odd
else {
if (arr[mid] == arr[mid - 1])
search(arr, mid + 1, high);
else
search(arr, low, mid - 1);
}
}
// Driver Code
var arr = [1, 1, 2, 4, 4, 5, 5, 6, 6];
var len = arr.length;
search(arr, 0, len - 1)
// This is code is contributed
// by shubhamsingh10
</script>
C++
#include <iostream>
using namespace std;
int search(int nums[], int n)
{
// A Binary Search based method to find the element
// that appears only once
int start = 0, end = n - 1, mid;
// For Edge Cases
if (n == 1) // If only one element is in the array
return nums[0];
if (nums[start]
!= nums[start + 1]) // If the first element
// is the element that
// appears only once
return nums[start];
if (nums[end]
!= nums[end - 1]) // If Last element is the element
// that appears only once
return nums[end];
// Binary Search
while (start <= end)
{
mid = start + (end - start) / 2;
// CASE 1
if (nums[mid] != nums[mid - 1]
&& nums[mid] != nums[mid + 1])
return nums[mid];
// CASE 2 and CASE 3
else if ((nums[mid] == nums[mid + 1]
&& mid % 2 == 0)
|| (nums[mid] == nums[mid - 1]
&& mid % 2 != 0))
start = mid + 1;
// CASE 4 and CASE 5
else
end = mid - 1;
}
// If no such element found
return -1;
}
// Driver code
int main()
{
int arr[] = { 1, 1, 2, 4, 4, 5, 5, 6, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
int element = search(arr, n);
if (element != -1)
cout << "The required element is " << element;
else
cout << "There is no such element";
}
// This code is contributed by umadevi9616
Java
class GFG {
public static int search(int[] nums)
{
// A Binary Search based method to find the element
// that appears only once
int start = 0, end = nums.length - 1, mid;
// For Edge Cases
if (nums.length
== 1) // If only one element is in the array
return nums[0];
if (nums[start]
!= nums[start + 1]) // If the first element
// is the element that
// appears only once
return nums[start];
if (nums[end]
!= nums[end
- 1]) // If Last element is the element
// that appears only once
return nums[end];
// Binary Search
while (start <= end) {
mid = start + (end - start) / 2;
// CASE 1
if (nums[mid] != nums[mid - 1]
&& nums[mid] != nums[mid + 1])
return nums[mid];
// CASE 2 and CASE 3
else if ((nums[mid] == nums[mid + 1]
&& mid % 2 == 0)
|| (nums[mid] == nums[mid - 1]
&& mid % 2 != 0))
start = mid + 1;
// CASE 4 and CASE 5
else
end = mid - 1;
}
// If no such element found
return -1;
}
public static void main(String[] args)
{
int[] arr = { 1, 1, 2, 4, 4, 5, 5, 6, 6 };
int element = search(arr);
if (element != -1)
System.out.println("The required element is "
+ element);
else
System.out.println("There is no such element");
}
}
// Code Contributed by Arnav Sharma
Python3
def search(nums):
# A Binary Search based method to find the element
# that appears only once
start = 0;
end = len(nums)-1;
mid = 0;
# For Edge Cases
if (len(nums) == 1): # If only one element is in the array
return nums[0];
if (nums[start] != nums[start + 1]): # If the first element
# is the element that
# appears only once
return nums[start];
if (nums[end] != nums[end - 1]): # If Last element is the element
# that appears only once
return nums[end];
# Binary Search
while (start <= end):
mid = start + (end - start) // 2;
# CASE 1
if (nums[mid] != nums[mid - 1] and nums[mid] != nums[mid + 1]):
return nums[mid];
# CASE 2 and CASE 3
elif((nums[mid] == nums[mid + 1] and mid % 2 == 0) or (nums[mid] == nums[mid - 1] and mid % 2 != 0)):
start = mid + 1;
# CASE 4 and CASE 5
else:
end = mid - 1;
# If no such element found
return -1;
# Driver code
if __name__ == '__main__':
arr = [ 1, 1, 2, 4, 4, 5, 5, 6, 6 ];
element = search(arr);
if (element != -1):
print("The required element is " , element);
else:
print("There is no such element");
# This code is contributed by umadevi9616
C#
using System;
public class GFG {
public static int search(int[] nums)
{
// A Binary Search based method to find the element
// that appears only once
int start = 0, end = nums.Length - 1, mid;
// For Edge Cases
if (nums.Length
== 1) // If only one element is in the array
return nums[0];
if (nums[start]
!= nums[start + 1]) // If the first element
// is the element that
// appears only once
return nums[start];
if (nums[end]
!= nums[end
- 1]) // If Last element is the element
// that appears only once
return nums[end];
// Binary Search
while (start <= end)
{
mid = start + (end - start) / 2;
// CASE 1
if (nums[mid] != nums[mid - 1]
&& nums[mid] != nums[mid + 1])
return nums[mid];
// CASE 2 and CASE 3
else if ((nums[mid] == nums[mid + 1]
&& mid % 2 == 0)
|| (nums[mid] == nums[mid - 1]
&& mid % 2 != 0))
start = mid + 1;
// CASE 4 and CASE 5
else
end = mid - 1;
}
// If no such element found
return -1;
}
public static void Main(String[] args)
{
int[] arr = { 1, 1, 2, 4, 4, 5, 5, 6, 6 };
int element = search(arr);
if (element != -1)
Console.WriteLine("The required element is "
+ element);
else
Console.WriteLine("There is no such element");
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
function search(nums)
{
// A Binary Search based method to find the element
// that appears only once
var start = 0, end = nums.length - 1, mid;
// For Edge Cases
if (nums.length
== 1) // If only one element is in the array
return nums[0];
if (nums[start]
!= nums[start + 1]) // If the first element
// is the element that
// appears only once
return nums[start];
if (nums[end]
!= nums[end
- 1]) // If Last element is the element
// that appears only once
return nums[end];
// Binary Search
while (start <= end)
{
mid = start + (end - start) / 2;
// CASE 1
if (nums[mid] != nums[mid - 1]
&& nums[mid] != nums[mid + 1])
return nums[mid];
// CASE 2 and CASE 3
else if ((nums[mid] == nums[mid + 1]
&& mid % 2 == 0)
|| (nums[mid] == nums[mid - 1]
&& mid % 2 != 0))
start = mid + 1;
// CASE 4 and CASE 5
else
end = mid - 1;
}
// If no such element found
return -1;
}
var arr = [ 1, 1, 2, 4, 4, 5, 5, 6, 6 ];
var element = search(arr);
if (element = 2)
document.write("The required element is "
+ element);
else
document.write("There is no such element");
// This code is contributed by shivanisinghss2110
</script>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA