Question

Create a List object that uses the binary search algorithm to search for the string "A". Display a message box indicating whether the value was found.

Language: C#

Answer 1

The Collection classes are a group of classes designed specifically for grouping together objects and performing tasks on them. List class is a collection and defined in the System.Collections.Generic namespace and it provides the methods and properties like other Collection classes such as add, insert, remove, search etc. It's the replacement for arrays, linked lists, queues, and most other one-dimensional data structures. This is because it has all kinds of extra functionality, including the ability to grow in size on-demand .

The C# List class represents a strongly typed list of objects that can be accessed by index and it supports storing values of a specific type without casting to or from object.

Step 1

Binary search algorithm:

A binary search algorithm is an algorithm that is more efficient than a sequential search algorithm.

• It requires the elements in the array should be arranged in ascending order.

• The searching process starts in the middle of the array.
• In the searching process, the algorithm finds an item or eliminates half of the array in each comparison.
• If the search item is less than the middle item, then it eliminates the second half of the array and it continues to search in the first half of the array.
• If the search item is greater than the middle item, then it eliminates the first half of the array and continues to search in the second half of the array.
• Once again, it examines the middle and repeats the above steps to find an item.
• If the middle item is equal to the search item, then the searching process is stopped.
• The search is stopped when an item is found or the search reaches the empty portion of the array.
• Divide and conquer is the strategy for binary search.
  • It divides large problems into smaller units.

• It minimizes the number of elements to be searched for the desired value.

Step 2

Algorithm:

Algorithm to search the string “A” using binary search algorithm in list is as follows:

• Declare the list object with “String” data type and add the items to list.
• The BinarySearch() method takes the inputs parameters of list and search value.
  • Check the middle value is equal to search value. If yes, display the message box with value was found.
  • Otherwise, check if the middle value is greater than search value. If yes, set the last value to search the search item. Because, the search value is in lower half of list.
  • Otherwise, set the last value to search the search item. Because, the search value is in upper half of list.

Step 3
Program:

Program to search the string “A” using binary search algorithm in list is as follows:

//Include libraries

using System;

using System.Collections.Generic;

using System.ComponentModel;

using System.Data;

using System.Drawing;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

using System.Windows.Forms;

 

//Define namespace

namespace WindowsFormsApp4

{

    //Define a class

    public partial class Form1 : Form

    {

          //Define a constructor for class

          public Form1()

          {

              //Call the InitializeComponent() method

              InitializeComponent();

          }

 

          //Declare and initialize list variable

          List<string> bsList = new List<string>();

 

          //Define the Form1_Load() method

private void Form1_Load(object sender, EventArgs e)

          {

              //Add the inputs to list

              bsList.Insert(0, "b");

              bsList.Insert(1, "A");

              bsList.Insert(2, "C");

              bsList.Insert(3, "e");

    
               Console.WriteLine("The Original List is:"); 

              //Loop executes until the list

              foreach(string s in bsList)

              {

                   //Add the items into the list box

                   listBox1.Items.Add(s);

              }

          }

 

          //Define the BinarySearch() method

         public static object BinarySearchDisplay(int[] arr, int key) 
        
         {
   
            int minNum = 0;
   
            int maxNum = arr.Length - 1;

       while (minNum <=maxNum) 
        {
             int mid = (minNum + maxNum) / 2;
      
              if (key == arr[mid])
        {
         
                   return ++mid;
      } 
          else if (key < arr[mid]) {
         
             max = mid - 1;
      }     
              else 
{
         min = mid + 1;
      }
   }
   return "None";
}

        Console.WriteLine("\nThe List in Sorted form"); 
          
        // sort the List 
             
                bslist.Sort(); 
      
  
        Console.WriteLine(); 
        
               foreach(string bs in bslist) 
        { 
            // prints the sorted List 
            
             Console.WriteLine(bs); 
              
        } 
           if (bslist.Contains("A"))
          
           {
        

         MessageBox.Show("Alphabet A exist in the list");
      }
      
                else
      {
         
           MessageBox.Show("Not exist");
}
}
}

output

The Original List is:

b

A

C

e

The List in Sorted form

A

b

C

e

Alphabet A exist in the list