Question 4 of 8intermediate🔧 ApplyLong Answer5 marks

Write a program that takes as input a list of 10 integers and a key value and applies binary search to find whether the key is present in the list or not. If the key is present it should display the position of the key in the list otherwise it should print an appropriate message. Run the program for at least 3 different key values and note the results.

Correct Answer

Program:

def binarySearch(list, key): first = 0 last = len(list) - 1 while(first <= last): mid = (first + last)//2 if list[mid] == key: return mid elif key > list[mid]: first = mid + 1 elif key < list[mid]: last = mid - 1 return -1

list1 = [] print("Enter 10 integers in ascending order:") for i in range(10): num = int(input("Enter element: ")) list1.append(num)

key = int(input("Enter the key to be searched: ")) pos = binarySearch(list1, key)

if(pos != -1): print(key, "is found at position", pos+1) else: print(key, "is not found in the list")

Sample Run 1: Enter 10 integers in ascending order: 2, 3, 5, 7, 10, 11, 12, 17, 19, 23 Enter the key to be searched: 17 17 is found at position 8

Sample Run 2: Enter 10 integers in ascending order: 2, 3, 5, 7, 10, 11, 12, 17, 19, 23 Enter the key to be searched: 2 2 is found at position 1

Sample Run 3: Enter 10 integers in ascending order: 2, 3, 5, 7, 10, 11, 12, 17, 19, 23 Enter the key to be searched: 15 15 is not found in the list

Exercise: EXERCISE | Q: 4 | (Page Page 15)
For More Understanding

Explanation

The program implements binary search algorithm as described in the textbook. The function binarySearch() takes a sorted list and key as parameters. It initializes first=0 and last=len(list)-1. Inside the while loop, mid is calculated as (first+last)//2. If list[mid]==key, the position is returned. If key>list[mid], first becomes mid+1; if key<list[mid], last becomes mid-1. If key is not found, -1 is returned. The main program creates a list of 10 integers in ascending order (required for binary search), accepts a key, calls the function, and displays appropriate message based on the returned position.

Solution Steps

  1. Step 1: Define binarySearch function with parameters list and key

  2. Step 2: Initialize first=0 and last=len(list)-1

  3. Step 3: Calculate mid=(first+last)//2 inside while loop

  4. Step 4: Compare key with list[mid] and adjust first/last accordingly

  5. Step 5: Return mid if found, -1 if not found

  6. Step 6: In main, accept 10 integers in ascending order and key value

  7. Step 7: Call binarySearch and display result with appropriate message

PreviousNext