Question

Consider the sorted array myList of integers below.

2 5 21 25 35 40 45 48 70 75 89 99

The Binary Search algorithm uses two index variables first and last to determine the position
(stored in another index variable mid) to search for an element. Using Binary Search to search
for the element 75 in myList, give the values of myList[first], myList[mid] and
myList[last] (in the form of a table) every time a new value is calculated for mid.

Answer 1

The values for the first, last, and mid values using the Binary Search Algorithm to search for 75 is as follows:

First	Last	Mid
2	99	40
45	99	70
75	99	89
75	75	75

The program terminates when mid value=75(the value to be found).

The binary search algorithm computes the middle value and then checks if the value to be found is equal, less, or greater than the value present at the mid index.

If the value is less than mylist[mid], the program updates the last index to mid-1.

If the value is greater than mylist[mid], the program updates the first index to mid+1.

If the value is equal to mylist[mid], the program returns the index.

I'm also attaching a sample code of the Binary Search Algorithm for you to test these values:

#include<bits/stdc++.h> 
#include<iostream>
using namespace std; 

int binary_search(int mylist[], int first, int last, int val)
{
        while(first <= last) { 
          cout<<"first="<<mylist[first] <<" " << "last="<<mylist[last]<<endl;       
  
    int mid=first+(last-first)/2; 
                cout<<"mid="<<mylist[mid] <<endl;
    
                if(mylist[mid]==val) 
                        return mid; 
                if(mylist[mid]<val) 
                        first=mid+1;
                else
                        last=mid-1; 
        } 
        return -1; 
} 

int main() 
{ 
        int mylist[]={ 2 ,5, 21, 25, 35, 40, 45, 48, 70, 75, 89, 99 }; 
        int val=75; 
        int size=sizeof(mylist)/sizeof(mylist[0]); 
        int index=binary_search(mylist,0,size-1,val); 
    if(index==-1)
       cout<<"Element not found";
    else
       cout<<"Element found at index"<<index;
        return 0; 
} 

Please find a photo of the code and output for your reference: