Register

Find the element that appears once in a sorted array.

• edited by
3,210 views
1 1 vote

In a sorted array, every element is repeated more than once except one. what will be the time complexity to find that element in the worst case?

1 Answer

0 0 votes
My ans is O(N)

we can not apply binary search here  because after divided  in binary search we should clearly know that which direction we go further either right  of left but here it is not possible element can be present in both direction. so we have to apply linear search to find that element.

Here question is little bit tricky because  in given question array is sorted. but array is sorted it does not mean that we have to apply binary search for finding element.
Voting & Accepting an answer helps improve the community
← Previous · programmingNext → · #Disk
← Previous in category · Bellman Ford algorit...Next in category → · Minimum Spanning tre...
Position:
Show:

Related questions

2 2 votes
1 1 answer
2.2k
2.2k views
yes asked Oct 6, 2015
2,191 views
the minimum no of comparisons required to find Majority Element in a sorted array (note that key is not given).
for example array contain a[1 2 3 3 3 3 3 4 5] then retun(1)
9 9 votes
2 answers 2 answers
23.4k
23.4k views
radha gogia asked Jul 19, 2015
23,398 views
Given an unsorted array. The array has this property that every element in array is at most k distance from its position in sorted array where k is a positive integer smaller than size of array. Which sorting algorithm can be easily modified for sorting this array and what is the obtainable time complexity?
(A) Insertion Sort with time complexity O(kn)(B) Heap Sort with time complexity O(nLogk)(C) Quick Sort with time complexity O(kLogk)(D) Merge Sort with time complexity O(...
0 0 votes
2 2 answers
4.5k
4.5k views
Saurabh Gupta 1 asked Jul 28, 2015
4,529 views
If we have two sorted array of size 'a' and 'b' and "one array smallest element is greater than largest element of other one".Then in the merge procedure, what will be its time complexity?
P.S. Applied conditions given in " " is applicable on any(as per choice)
0 0 votes
2 2 answers
1.9k
1.9k views
dhruba asked Jun 5, 2023
1,889 views
Binary search is performed on a sorted array of n elements. The search key is not in the array and falls between the elements at positions m and m+1 (where 1 ≤ m < n). How many comparisons are needed in the worst case scenario to determine that the key is not in the array?
Binary search is performed on a sorted array of n elements. The search key is not in the array and falls between the elements at positions m and m+1 (where 1 ≤ m < n). Ho...