Repository navigation
Expand file tree
/
Copy pathbinary_search.py
More file actions
55 lines (44 loc) · 1.8 KB
/
Copy pathbinary_search.py
File metadata and controls
55 lines (44 loc) · 1.8 KB
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
# It returns location of x in given array arr
# if present, else returns -1
def binarySearch(arr, left, right, x):
"""
Perform a binary search on the given sorted array to find the location
of the target value x.
Parameters:
arr (list): The sorted array in which to perform the binary search.
left (int): The leftmost index of the search range.
right (int): The rightmost index of the search range.
x (int): The target value to be searched in the array.
Returns:
int: The index of the target value x in the array if found, otherwise returns -1.
"""
while left <= right:
mid = left + (right - left) // 2 # extracting the middle element from the array
mid = int(mid) # it has to be integer
# Check if x is present at mid
if arr[mid] == x:
return mid
# If x is greater, ignore left half
if arr[mid] < x:
# move left past the middle so the next search starts from there
left = mid + 1
# If x is smaller, ignore right half
elif x < arr[mid]:
# move right before the middle so the next search stops there
right = mid - 1
# If we reach here, then the element was not present
return -1
# Main Function
if __name__ == "__main__":
# User input array
print("Enter the array with comma separated in which element will be searched")
# the input array is of int type, with elements separated by commas
arr = [int(x) for x in input().split(',')]
x = int(input("Enter the element you want to search in given array"))
# Function call
result = binarySearch(arr, 0, len(arr) - 1, x)
#printing the output
if result != -1:
print(f"Element is present at index {result}")
else:
print("Element is not present in array")