Searching Inclass Problems
1. Smart Library: Finding Books with Binary Search
n=int(input())
arr=list(map(int,input().split()))
element=int(input())
def binary_search(arr,element):
l=0
r=n-1
while l<=r:
m=(l+r)//2
if arr[m]==element:
return m
elif arr[m]<element:
l=m+1
else:
r=m-1
return -1
res=binary_search(arr,element)
print(res)
2. Treasure Hunt: Searching in a Rotated Map
n = int(input())
arr = list(map(int, input().split()))
element = int(input())
def search_rotated(arr, element):
l=0
r=n-1
while l <= r:
m = (l + r) // 2
if arr[m] == element:
return m
# Left half is sorted
if arr[l] <= arr[m]:
if arr[l] <= element < arr[m]:
r=m-1
else:
l=m+1
# Right half is sorted
else:
if arr[m] < element <= arr[r]:
l=m+1
else:
r=m-1
return -1
print(search_rotated(arr, element))
3. Log Analysis: Finding First and Last Occurrence of an Event
def first(nums, target):
l=0
r = len(nums) - 1
while l <= r:
mid = (l + r) // 2
if nums[mid] < target:
l = mid + 1
else:
r = mid - 1
return l
def last(nums, target):
l=0
r = len(nums) - 1
while l <= r:
mid = (l + r) // 2
if nums[mid] <= target:
l = mid + 1
else:
r = mid - 1
return r
# Input
n = int(input())
if n == 0:
print([-1, -1])
else:
nums = list(map(int, input().split()))
target = int(input())
l1 = first(nums, target)
l2 = last(nums, target)
if l1 <= l2 and l1 < len(nums) and nums[l1] == target:
print([l1, l2])
else:
print([-1, -1])
4. Product Inventory Search in a Warehouse
m,n=map(int,input().split())
matrix=[]
for _ in range(m):
row=list(map(int,input().split()))
[Link](row)
element=int(input())
def search_matrix(matrix, element):
if not matrix or not matrix[0]:
return -1
rows = len(matrix)
cols = len(matrix[0])
left = 0
right = rows * cols - 1
while left <= right:
mid = (left + right) // 2
row = mid // cols
col = mid % cols
mid_val = matrix[row][col]
if mid_val == element:
return True
elif mid_val < element:
left = mid + 1
else:
right = mid - 1
return False
res=search_matrix(matrix, element)
if res == True:
print('true')
else:
print('false')
5. Finding the Oldest Artifact in a Rotated Historical Timeline
n = int(input())
arr = list(map(int, input().split()))
def find_min_in_rotated(arr):
left, right = 0, len(arr) - 1
while left < right:
mid = (left + right) // 2
if arr[mid] > arr[right]:
left = mid + 1
else:
right = mid
return arr[left]
print(find_min_in_rotated(arr))
6. Finding the Highest Mountain Peak in a Terrain Map
n = int(input())
array = list(map(int, input().split()))
def find_peak(arr):
left = 0
right = len(arr) - 1
while left < right:
mid = (left + right) // 2
if arr[mid] < arr[mid + 1]:
left = mid + 1
else:
right = mid
return left
print(find_peak(array))
7. Finding Two Numbers Whose Squares Sum to a Given Value
num = int(input())
def check_sum_of_squares(num):
if num < 0:
return False
for a in range(int(num ** 0.5) + 1):
b2 = num - a * a
left = 0
right = int(b2 ** 0.5) + 1
while left <= right:
mid = (left + right) // 2
square = mid * mid
if square == b2:
return True
elif square < b2:
left = mid + 1
else:
right = mid - 1
return False
print(str(check_sum_of_squares(num)).lower())