POP Lab Manual

Program 5

Implement Binary Search algorithm to efficiently search for a specific integer element in a sorted array. Binary search works by repeatedly dividing the search interval in half, comparing the target with the middle element, and eliminating half of the remaining elements with each iteration.
Key Concepts:
Time Complexity: O(log n)
Space Complexity: O(1)
Requirement: Sorted Array
Middle Index: (low + high) / 2

Algorithm

  1. Initialize: Start the program and declare variables
  2. Input Size: Read the number of elements in the array
  3. Input Array: Read n sorted integers into the array
  4. Input Search Key: Read the element to be searched
  5. Set Boundaries: Initialize low = 0, high = n-1, found = 0
  6. Binary Search Loop: While low ≤ high, calculate mid = (low + high) / 2
  7. Compare & Update: If arr[mid] == key, set found = 1; else update low or high
  8. Display Result: Show position if found, else show "not found" message
  9. Terminate: End the program

Flowchart

START
→
Input n, array
→
Input key
→
low=0, high=n-1
→
While low≤high
→
mid=(low+high)/2
→
Compare & Update
→
Display Result
→
STOP

Code 

#include <stdio.h>


int main() {
    int n, i, key, low, high, mid;
    
    printf("Enter number of elements: ");
    scanf("%d", &n);

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

    printf("Enter element to search: ");
    scanf("%d", &key);

    low = 0;
    high = n - 1;
    int found = 0;

    while (low <= high) {
        mid = (low + high) / 2;

        if (arr[mid] == key) {
            printf("Element %d found at position %d\n", key, mid + 1);
            found = 1;
            break;
        }
        else if (arr[mid] < key)
            low = mid + 1;
        else
            high = mid - 1;
    }

    if (!found)
        printf("Element %d not found in the array.\n", key);

    return 0;
}

Sample Output 


// Output 1 - Element Found
Enter number of elements: 7
Enter 7 sorted elements:
10 20 30 40 50 60 70
Enter element to search: 40
Element 40 found at position 4

// Output 2 - Element Not Found
Enter number of elements: 5
Enter 5 sorted elements:
5 15 25 35 45
Enter element to search: 30
Element 30 not found in the array.

// Output 3 - First Element Search
Enter number of elements: 6
Enter 6 sorted elements:
1 3 7 12 18 25
Enter element to search: 1
Element 1 found at position 1

// Output 4 - Last Element Search
Enter number of elements: 8
Enter 8 sorted elements:
2 4 6 8 10 12 14 16
Enter element to search: 16
Element 16 found at position 8

// Output 5 - Single Element Array
Enter number of elements: 1
Enter 1 sorted elements:
42
Enter element to search: 42
Element 42 found at position 1
Comments

Replay !

0 Comments

Share Your Thoughts

Please enter your name
Please enter a valid email
Password must be at least 6 characters
Please enter your comment
0/500 characters
Email Verification Required
We've sent a 6-digit verification code to . Please enter the code below to verify your email address.
Email Verified Successfully!
Your email has been verified. Would you like to proceed with posting your comment?

Type "YES" to confirm and post your comment, or click Cancel to skip posting.