FilesExpand file tree

 main

/

singleElementInSortedArray.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

69 lines (55 loc) · 2.64 KB

 main

/

singleElementInSortedArray.py

Copy path

Top

File metadata and controls

• Code
• Blame

69 lines (55 loc) · 2.64 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

# https://leetcode.com/problems/single-element-in-a-sorted-array/

# Algorithm - Binary Search

# apply binary search

# if mid is a non extreme element (mid!=0 and mid!=len(arr)) => arr[mid]!=arr[mid-1] and arr[mid]!=arr[mid+1] =>return arr[mid]

# if mid==0, if arr[mid] != arr[mid +1] => return arr[mid]

# if mid==n-1, if arr[mid] != arr[mid-1] => return arr[mid]

# if mid is even, move to the side of the element same as mid

# if mid is odd, move to side of the element different from mid

class Solution:

def singleNonDuplicate(self, nums) -> int:

# n represents the size of the array

n = len(nums)

# if the size of the array is 1, the only element available is our answer

if n == 1:

return nums[0]

# initially start is the first index of the array

start = 0

# initially end is the last index of the array

end = n - 1

while start <= end:

mid = start + (end-start)//2

# if mid is the start index and if element at mid is different from element at mid+1

# then element at mid is our answer

if mid == 0 and nums[mid]!=nums[mid+1]:

return nums[mid]

# if mid is the last index of the array and if element at mid is different from element at mid-1

# then element at mid is our answer

if mid == n - 1 and nums[mid] != nums[mid-1]:

return nums[mid]

# if mid is an index somewhere in the middle of the array

# if element at mid is different from elements at mid-1 and mid+1

# then mid is our answer

if nums[mid] != nums[mid-1] and nums[mid] != nums[mid+1]:

return nums[mid]

# now we have cases to move the start and end pointers

# if mid is even - even number of elements to the left of mid

if mid%2 == 0:

# if element at mid is equal to element at mid+1

# ans will lie to the right of mid

# start = mid + 1

# else end = mid - 1

if nums[mid] == nums[mid+1]:

start = mid + 1

else:

end = mid - 1

# if mid is odd - odd number of elements to the left of mid

else:

# if element at mid is not equal to element at mid-1

# then our ans lies to the right side of mid

# so start = mid + 1

# else end = mid - 1

if nums[mid] != nums[mid + 1]:

start = mid + 1

else:

end = mid - 1