Question

Q2 - 15 pts) Given a minimum unimodal array of integers, run the binary search algorithm to find the minimum element. You need to show the initial and the iteration-level values of the left index, right index and middle index as well as your decisions to reduce the search space in each iteration.

0

1

2

3

4

5

6

7

8

9

33

32

27

26

24

22

21

8

7

3

Answer 1

Python Code

def findMin(arr, low, high): # Function to find minimum element
  
while (low < high):
mid = low + (high - low) // 2;
  
if (arr[mid] == arr[high]):
high -= 1;
elif (arr[mid] > arr[high]):
low = mid + 1;
else:
high = mid;
return arr[high];
  

if __name__ == '__main__': # Driver code
  
arr = [33, 32, 27, 26, 24, 22, 21, 8, 7, 3];
n = len(arr);
print("The minimum element is : ", findMin(arr, 0, n - 1));

Output

The minimum element is : 3

Iterations:

33 32 27 26 24 22 21 8 7 3 - Array Elements

0 1 2 3 4 5 6 7 8 9 - Index

Iteration 1:

low = 0 high = 9

while( 0<9 ) //True

mid = 0 + (9-0) //2 = 4

if( a[4]==[9] )

24 == 3 //False

elif( a[4]>a[9] )

24>3 //True

low = 4+1 = 5

Iteration 2:

while( 5<9 ) //True

mid = 5 + (9-5) //2 = 7

if( a[7]==[9] )

8==3 //False

elif( a[7]>a[9] )

8>3 //True

low = 7+1= 8

Iteration 3:

while(8<9) //True

mid=8+(9-8)//2=8

if(a[8]==[9])

7==3 //False

elif(a[8]>a[9])

7>3 //True

low=8+1=9

Iteration 4:

while(9>9) // False

return a[9]

return 3