C Program to Implement Binary Search Using Pointers

Introduction

Binary Search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing the search interval in half. If the value of the search key is less than the item in the middle of the interval, the search continues in the lower half, or if the value is greater, it continues in the upper half. In C, you can implement Binary Search using pointers to directly manipulate the elements of the array. This guide will show you how to write a C program to implement Binary Search using pointers.

Example:

• Input: Sorted array [1, 2, 5, 7, 9, 12, 15], Target 9
• Output: Element 9 found at position 4

Problem Statement

Create a C program that:

• Takes a sorted array of integers and a target element as input from the user.
• Uses pointers to implement the Binary Search algorithm to find the target element.
• Displays whether the target element was found and its position.

Solution Steps

1. Include the Standard Input-Output Library: Use #include <stdio.h> for standard input-output functions.
2. Declare the Array and Pointer Variables: Declare an integer array to store the elements and pointers for accessing and manipulating the elements.
3. Input the Array Elements: Use a loop to take input for the array elements from the user.
4. Input the Target Element: Take the target element that needs to be searched in the array.
5. Implement Binary Search Using Pointers: Use pointers to perform the binary search on the array.
6. Display the Result: Use printf to display whether the target element was found and its position.

C Program to Implement Binary Search Using Pointers

#include <stdio.h>

int main() {
    // Step 2: Declare the array and pointer variables
    int arr[100], n, target;
    int *low_ptr, *high_ptr, *mid_ptr;

    // Step 3: Input the number of elements and the array elements
    printf("Enter the number of elements: ");
    scanf("%d", &n);

    printf("Enter the elements of the sorted array: ");
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }

    // Step 4: Input the target element to search for
    printf("Enter the element to search: ");
    scanf("%d", &target);

    // Step 5: Implement Binary Search using pointers
    low_ptr = arr;  // Initialize low_ptr to the start of the array
    high_ptr = arr + n - 1;  // Initialize high_ptr to the end of the array

    while (low_ptr <= high_ptr) {
        mid_ptr = low_ptr + (high_ptr - low_ptr) / 2;  // Calculate mid_ptr

        if (*mid_ptr == target) {
            printf("Element %d found at position %ld.\n", target, mid_ptr - arr);
            return 0;
        } else if (*mid_ptr < target) {
            low_ptr = mid_ptr + 1;  // Search in the right half
        } else {
            high_ptr = mid_ptr - 1;  // Search in the left half
        }
    }

    // If the element is not found
    printf("Element %d not found in the array.\n", target);

    return 0;  // Return 0 to indicate successful execution
}

Explanation

Step 2: Declare the Array and Pointer Variables

• The integer array arr is declared to store the elements of the array.
• The pointers low_ptr, high_ptr, and mid_ptr are used to traverse the array during the binary search.

Step 3: Input the Array Elements

• The program prompts the user to enter the number of elements in the array and stores this value in n.
• A for loop is used to take input for each element of the sorted array.

Step 4: Input the Target Element

• The program prompts the user to enter the target element that needs to be searched in the array.

Step 5: Implement Binary Search Using Pointers

• The pointer low_ptr is initialized to point to the first element of the array, and high_ptr is initialized to point to the last element.
• A while loop is used to perform the binary search:
  • The loop continues as long as low_ptr is less than or equal to high_ptr.
  • The mid_ptr is calculated as the midpoint between low_ptr and high_ptr.
  • The element pointed to by mid_ptr is compared with the target:
    • If they are equal, the target is found, and its position is printed.
    • If the element at mid_ptr is less than the target, the search continues in the right half by updating low_ptr.
    • If the element at mid_ptr is greater than the target, the search continues in the left half by updating high_ptr.
• If the loop exits without finding the target, a message indicating that the element was not found is displayed.

Step 6: Display the Result

• If the element is found, its position in the array is displayed. If not, a message indicating that the element was not found is printed.

Return 0

• The return 0; statement indicates that the program executed successfully.

Output Example

Example Output:

Enter the number of elements: 7
Enter the elements of the sorted array: 1 2 5 7 9 12 15
Enter the element to search: 9
Element 9 found at position 4.

Example Output (Element Not Found):

Enter the number of elements: 7
Enter the elements of the sorted array: 1 2 5 7 9 12 15
Enter the element to search: 10
Element 10 not found in the array.

Conclusion

This C program demonstrates how to implement Binary Search using pointers. It covers basic concepts such as pointer manipulation, array traversal, and efficient searching algorithms, making it a useful example for beginners learning C programming.