Binary Search Algorithm in Algol: A Program That Searches for a Specific Value in a Sorted List

The binary search algorithm is a widely used search algorithm that allows for the efficient searching of a sorted list of elements for a specific value. It works by repeatedly dividing the search interval in half until the value is found or the search interval is empty. In this article, we will show you how to write a program in Algol that implements the binary search algorithm to search for a specific value in a sorted list.

To implement the binary search algorithm in Algol, we will use a loop to repeatedly divide the search interval in half and check if the value we are searching for is in the left or right half. Here is the algorithm:

1. Start with a sorted list of n elements and the value we are searching for.
2. Initialize the left and right pointers to the first and last elements of the list, respectively.
3. Use a loop to repeatedly divide the search interval in half until the value is found or the search interval is empty.
4. If the value is found, return the index of the element.
5. If the value is not found, return -1.

Now let’s write the program in Algol:

begin
integer n, value, left, right, mid, i;
integer list[1:n];

write("Enter the number of elements in the list: ");
read(n);

write("Enter the sorted list: ");
for i := 1 step 1 until n do
    read(list[i]);

write("Enter the value to search for: ");
read(value);

left := 1;
right := n;

while left <= right do
    mid := (left + right) div 2;
    if list[mid] = value then
        return mid;
    elsif list[mid] < value then
        left := mid + 1;
    else
        right := mid - 1;
    fi
od

return -1;

end.

In this program, we first declare six variables: n, value, left, right, mid, and i. n is the number of elements in the list, value is the value we are searching for, left and right represent the search interval, mid is the index of the middle element, and i is a loop counter.

We then prompt the user to enter the number of elements in the list and read it into the variable n. We also prompt the user to enter the sorted list and read each element into the list array.

Next, we prompt the user to enter the value they are searching for and read it into the variable value.

We then initialize the left pointer to the first element of the list and the right pointer to the last element of the list.

We then use a while loop to repeatedly divide the search interval in half until the value is found or the search interval is empty. We calculate the index of the middle element using the formula (left + right) div 2. If the middle element is equal to the value we are searching for, we return the index of the middle element. If the middle element is less than the value we are searching for, we update the left pointer to mid + 1. Otherwise, we update the right pointer to mid – 1.

Finally, if the value is not found, we return -1.

Let’s try running the program with the following inputs:

Suppose we have the following inputs:

Enter the number of elements in the list: 10
Enter the sorted list: 1 3 5 7 9 11 13 15 17 19
Enter the value to search for: 7

The program will perform the following steps:

1. Set n to 10, and read the sorted list of elements into the array list.
2. Set value to 7.
3. Set left to 1, and right to 10.
4. Begin the while loop, where left <= right.
5. Calculate the index of the middle element using the formula (left + right) div 2. This gives us 5.
6. Check if list[5] = value. Since 11 is not equal to 7, we continue to step 7.
7. Check if list[5] < value. Since 11 is greater than 7, we update right to 4.
8. Calculate the index of the new middle element using the formula (left + right) div 2. This gives us 2.
9. Check if list[2] = value. Since 3 is not equal to 7, we continue to step 10.
10. Check if list[2] < value. Since 3 is less than 7, we update left to 3.
11. Calculate the index of the new middle element using the formula (left + right) div 2. This gives us 3.
12. Check if list[3] = value. Since 7 is equal to 7, we return 3.

Therefore, the program will output 3, which is the index of the value 7 in the sorted list.

In conclusion, the binary search algorithm is a powerful and efficient search algorithm that can be used to search for a specific value in a sorted list. In this article, we have shown you how to implement the binary search algorithm in Algol using a step-by-step approach and provided sample code to help you get started. By following these instructions, you can create your own program to search for specific values in sorted lists using the binary search algorithm.

Share on Facebook

Tweet

Follow us

Save