Given a sorted array containing only 0s and 1s, find the transition point. 
Example 1:
Input:
N = 5
arr[] = {0,0,0,1,1}
Output: 3
Explanation: index 3 is the transition 
point where 1 begins.
Example 2:
Input:
N = 4
arr[] = {0,0,0,0}
Output: -1
Explanation: Since, there is no "1",
the answer is -1.
Your Task:
You don't need to read input or print anything. The task is to complete the function transitionPoint() that takes array and N as input parameters and returns the 0 based index of the position where "0" ends and "1" begins. If array does not have any 1s, return -1. If array does not have any 0s, return 0.
Expected Time Complexity: O(LogN)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 500000
0 ≤ arr[i] ≤ 1

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Complete search

Starter code: def transitionPoint(arr, n):

    #Code here

Solutions:
from bisect import bisect_left

def transitionPoint(arr, n):
	if arr[0] == arr[-1] == 0:
		return -1
	if arr[0] == arr[-1] == 1:
		return 0
	return bisect_left(arr, 1)


def transitionPoint(arr, n):
	start = 0
	res = -1
	end = len(arr) - 1
	while start <= end:
		mid = (start + end) // 2
		if arr[mid] == 1:
			res = mid
			end = mid - 1
		elif arr[mid] == 0:
			start = mid + 1
	return res


def transitionPoint(arr, n):
	l = 0
	r = n - 1
	while l <= r:
		a = int((l + r) / 2)
		if arr[a] == 0:
			l = a + 1
		elif arr[a] == 1:
			if a == 0 or (a > 0 and arr[a - 1] == 0):
				return a
			r = a - 1
	return -1


def transitionPoint(arr, n):
	s = arr[0]
	e = len(arr) - 1
	if arr[0] == 1:
		return 0
	while s <= e:
		m = (s + e) // 2
		if arr[m] == 0:
			s = m + 1
		elif arr[m] == 1:
			if arr[m - 1] == 0:
				return m
			e = m - 1
	return -1


def transitionPoint(arr, n):
	if arr[0] == 1:
		return 0
	lb = 0
	ub = n - 1
	while lb <= ub:
		mid = int((lb + ub) / 2)
		if arr[mid] == 0:
			lb = mid + 1
		elif arr[mid] == 1:
			if arr[mid - 1] == 0:
				return mid
			ub = mid - 1
	return -1


def transitionPoint(arr, n):
	for i in range(n):
		if arr[i] == 1:
			return i
	else:
		return -1


def transitionPoint(array, n):
	(low, high) = (0, n - 1)
	while low <= high:
		mid = (low + high) // 2
		if array[mid] == 0:
			low = mid + 1
		else:
			if mid == 0 or array[mid - 1] != array[mid]:
				return mid
			high = mid - 1
	return -1


def transitionPoint(arr, n):
	if n == 1 and arr[0] == 1:
		return 0
	elif n == 1 and arr[0] == 0:
		return -1
	else:
		for i in range(n - 1):
			if arr[i] != arr[i + 1]:
				return i + 1
		return -1 if arr.count(1) == 0 else 0


def transitionPoint(arr, n):
	if 1 not in arr:
		return -1
	return arr.index(1)


def transitionPoint(arr, n):
	A = []
	for a in range(len(arr) - 1):
		if arr[a] != arr[a + 1] and len(A) == 0:
			A.append(a + 1)
	if all((elem == 1 for elem in arr)):
		result = 0
		return result
	elif all((elem == 0 for elem in arr)):
		result = -1
		return result
	else:
		return A[0]


def transitionPoint(arr, n):
	(l, r) = (0, n - 1)
	res = -1
	while l <= r:
		mid = (l + r) // 2
		if arr[mid] == 1:
			res = mid
			r = mid - 1
		else:
			l = mid + 1
	return res


def transitionPoint(arr, n):
	ans = 0
	s = True
	for i in range(n):
		if arr[i] == 1:
			ans = i
			break
	if arr.count(0) == n:
		return -1
	else:
		return ans


def transitionPoint(arr, n):
	for a in arr:
		if a == 1:
			return arr.index(a)
	return -1


def transitionPoint(arr, n):
	k = []
	for i in range(len(arr)):
		if arr[i] == 1:
			k.append(i)
			break
	if k:
		for j in k:
			return j
	else:
		return -1


def transitionPoint(arr, n):
	trp = -1
	for i in range(n):
		if arr[i] == 1:
			trp = i
			break
	return trp


def transitionPoint(arr, n):
	try:
		ind = arr.index(1)
		return ind
	except:
		return -1


def transitionPoint(arr, n):
	if len(set(arr)) == 1 and arr[0] == 0:
		return -1
	elif len(set(arr)) == 1 and arr[0] == 1:
		return 0
	else:
		return arr.index(list(set(arr))[1])


def transitionPoint(arr, n):
	if arr[0] == 1:
		return 0
	low = 0
	high = n - 1
	while low <= high:
		mid = (low + high) // 2
		if mid + 1 < n and arr[mid] == 0 and (arr[mid + 1] == 1):
			return mid + 1
		elif mid - 1 >= 0 and arr[mid] == 1 and (arr[mid - 1] == 0):
			return mid
		if mid + 1 < n and arr[mid] == 0 and (arr[mid + 1] == 0):
			low = mid + 1
		elif mid - 1 >= 0 and arr[mid] == 1 and (arr[mid - 1] == 1):
			high = mid
		else:
			return -1


def transitionPoint(arr, n):
	check = False
	for i in range(n):
		if arr[i] == 1:
			check = True
			return i
	if check == False:
		return -1
arr = [0, 0, 0, 1, 1]
transitionPoint(arr, 5)


def transitionPoint(arr, n):
	for i in range(n):
		if arr[i] != 0:
			return i
	return -1


def transitionPoint(arr, n):
	l = 0
	r = n - 1
	while l <= r:
		mid = int((l + r) / 2)
		if mid == n - 1 and arr[mid] == 0:
			return -1
		if mid == 0 and arr[mid] == 1:
			return 0
		if arr[mid] == 0 and arr[mid + 1] == 1:
			return mid + 1
		if arr[mid] == 0:
			l = mid + 1
		else:
			r = mid - 1


def transitionPoint(arr, n):
	i = 0
	j = n - 1
	if arr[n - 1] == 0:
		return -1
	if arr[0] == 1:
		return 0
	while i <= j:
		mid = (i + j) // 2
		if arr[mid] == 0:
			if arr[mid + 1] == 1:
				return mid + 1
			else:
				i = mid + 1
		elif arr[mid] == 1:
			if arr[mid - 1] == 0:
				return mid
			else:
				j = mid - 1
	return -1


def transitionPoint(arr, n):
	if arr[0] == 1:
		return 0
	if arr[n - 1] == 0:
		return -1
	low = 0
	n = n - 1
	mid = (low + n) // 2
	while low < n:
		if arr[mid] == 1:
			n = mid - 1
		else:
			low = mid + 1
		mid = (low + n) // 2
	if arr[mid] == 0:
		return mid + 1
	else:
		return mid


def transitionPoint(arr, n):
	arr.sort()
	if 1 in arr:
		return arr.index(1)
	else:
		return -1


def transitionPoint(arr, n):
	arr.sort()
	l = n - 1
	if arr[l] == 0:
		return -1
	elif arr[0] == 1:
		return 0
	else:
		while arr[l - 1] == 1:
			l = l - 1
	return l


def transitionPoint(arr, n):
	if arr[0] == 1:
		return 0
	leftIndex = 0
	rightIndex = n - 1
	while leftIndex <= rightIndex:
		midIndex = leftIndex + (rightIndex - leftIndex) // 2
		if arr[midIndex - 1] < arr[midIndex]:
			return midIndex
		if arr[midIndex] == 1:
			rightIndex = midIndex - 1
		else:
			leftIndex = midIndex + 1
	return -1


def transitionPoint(arr, n):
	start = 0
	end = n - 1
	while start <= end:
		mid = start + (end - start) // 2
		if arr[mid] == 1:
			if mid > 0 and arr[mid - 1] == 0 or mid == 0:
				return mid
			else:
				end = mid - 1
		elif arr[mid] == 0:
			if mid < n - 1 and arr[mid + 1] == 1:
				return mid + 1
			else:
				start = mid + 1
	return -1


def binary_search(arr, low, high):
	if high >= low:
		mid = (high + low) // 2
		if arr[mid] == 1 and arr[mid - 1] == 0:
			return mid
		elif arr[mid] == 1:
			return binary_search(arr, low, mid - 1)
		else:
			return binary_search(arr, mid + 1, high)
	else:
		return -1

def transitionPoint(arr, n):
	if n == 0 or arr[n - 1] == 0:
		return -1
	if arr[0] == 1:
		return 0
	return binary_search(arr, 0, n)


def transitionPoint(arr, n):
	for i in range(n):
		if arr[i] == 1:
			return i
			break
		elif arr[i] == 0:
			continue
	return -1


def transitionPoint(arr, n):
	l = 0
	r = n - 1
	if n == 1 and arr[0] == 0:
		return -1
	if n == 1 and arr[0] == 1:
		return 0
	while l <= r:
		mid = (l + r) // 2
		if arr[mid] == 1 and arr[mid - 1] == 0:
			return mid
		elif arr[mid] == 1:
			r = mid - 1
		else:
			l = mid + 1
	if len(arr) == -1:
		return 0
	if len(arr) == l:
		return -1
	return 0


def transitionPoint(arr, n):
	mid = int((n - 1) / 2)
	s = 0
	l = n - 1
	for i in range(n):
		if n == 1:
			if arr[0] == 0:
				return -1
			else:
				return 0
		elif arr[mid] == 0 and mid != n - 1:
			if arr[mid + 1] == 1:
				return mid + 1
				break
			else:
				s = mid + 1
				mid = int((s + l) / 2)
		elif arr[mid] == 1 and mid != 0:
			if arr[mid - 1] == 0:
				return mid
				break
			else:
				l = mid - 1
				mid = int((l + s) / 2)
		elif mid == n - 1:
			return -1
		else:
			return 0


def transitionPoint(arr, n):
	l = 0
	r = n - 1
	if len(arr) == 1 and arr[0] == 1:
		return 0
	if len(arr) == 1 and arr[0] == 0:
		return -1
	try:
		while l <= r:
			mid = (l + r) // 2
			if arr[mid] == 0:
				if arr[mid + 1] == 1:
					return mid + 1
				l = mid + 1
			elif arr[mid] == 1:
				if arr[mid - 1] == 0:
					return mid
				r = mid - 1
	except:
		pass
	if r == len(arr):
		return -1
	if l == 0:
		return 0
	return -1


def transitionPoint(arr, n):
	i = 0
	j = n - 1
	zero = -1
	one = -1
	while i <= j:
		m = (i + j) // 2
		if arr[m] == 0:
			zero = m
			i = m + 1
		elif arr[m] == 1:
			one = m
			j = m - 1
	if zero == -1:
		return 0
	if one == -1:
		return -1
	return one


def transitionPoint(arr, n):

	def findTransition(arr, i, j):
		if j < i:
			return -1
		m = (i + j) // 2
		if arr[m] == 1 and arr[m - 1] == 0:
			return m
		if arr[m] == 0 and arr[m + 1] == 1:
			return m + 1
		if arr[m] == 1:
			j = m - 1
			return findTransition(arr, i, j)
		if arr[m] == 0:
			i = m + 1
			return findTransition(arr, i, j)
	if arr[0] == 1:
		return 0
	if n == 1:
		return -1
	try:
		return findTransition(arr, 0, n)
	except:
		return -1


def transitionPoint(arr, n):
	if arr.count(0) == n:
		return -1
	if n == 1 and arr[0] == 1 or arr.count(1) == n:
		return 0
	for i in range(n):
		if i == n - 1:
			break
		elif arr[i] == arr[i + 1]:
			continue
		else:
			return i + 1
			break


def transitionPoint(arr, n):
	if arr.count(1) == 0:
		return -1
	else:
		return arr.index(1)


def transitionPoint(arr, n):
	for i in arr:
		if i == 1:
			return arr.index(i)
	return -1


def transitionPoint(arr, n):
	for i in range(n):
		if 1 not in arr:
			return -1
		return arr.index(1)


def transitionPoint(arr, n):
	l = 0
	u = n - 1
	while l <= u:
		mid = (l + u) // 2
		if arr[mid] == 0:
			l = mid + 1
		elif arr[mid] == 1:
			if mid == 0 or (mid > 0 and arr[mid - 1] == 0):
				return mid
			u = mid - 1
	return -1


def transitionPoint(arr, n):
	place = 0
	for i in range(len(arr)):
		if arr[i] == 0:
			place += 1
		else:
			return place
	return -1


def transitionPoint(arr, n):
	beg = 0
	end = n - 1
	mid = (end + beg) // 2
	i = -1
	while beg <= end:
		mid = (end + beg) // 2
		if arr[mid] == 1:
			i = mid
			end = mid - 1
		if arr[mid] == 0:
			beg = mid + 1
	return i


import math

def transitionPoint(arr, n):
	if arr[0] == 1:
		return 0
	if arr[-1] == 0:
		return -1
	(low, high) = (0, n - 1)
	mini = math.inf
	while low <= high:
		mid = (low + high) // 2
		if arr[mid] == 1:
			mini = min(mini, mid)
			high = mid - 1
		else:
			low = mid + 1
	return mini


def transitionPoint(arr, n):
	for i in range(len(arr)):
		if arr[i] == 1:
			return i
	return -1


def transitionPoint(arr, n):
	arr.sort()
	if 0 in arr and 1 not in arr:
		return -1
	if 1 in arr and 0 not in arr:
		return 0
	count = 0
	for i in range(0, n):
		if arr[i] == 0:
			count = count + 1
		else:
			return i
	if count == 0:
		return -1


def transitionPoint(arr, n):
	for (i, j) in enumerate(arr):
		if j == 1:
			return i
	return -1


def transitionPoint(arr, n):
	if n == 1 and arr[0]:
		return 0
	if n == 1 and (not arr[0]):
		return -1
	if arr[0]:
		return 0
	(l, r) = (0, n - 1)
	while l < r:
		mid = l + r // 2
		if arr[mid] == 1 and (not arr[mid - 1]):
			return mid
		if not arr[mid]:
			l += 1
		if arr[mid]:
			r -= 1
	return -1