Search in Sorted Array in C: Binary Search Program

📚 In this tutorial, you will learn:

What is binary search and how it works
How to implement binary search in C
How binary search is faster than linear search
Step-by-step explanation of the program
Practice exercises to test your understanding

Introduction

In this tutorial, we will learn how to write a C program to search an element in a sorted array using binary search.

Binary search is a fast searching algorithm that works on sorted arrays. It works by repeatedly dividing the search interval in half. If the target value is less than the middle element, the search continues in the left half; otherwise, it continues in the right half.

Binary search is used in many real-world applications, such as:

Searching in a phonebook (sorted by name)
Finding a word in a dictionary
Searching in a sorted database
Finding an element in a sorted list

💡 Key Point: Binary search is much faster than linear search. It has a time complexity of O(log n) compared to O(n) for linear search. However, the array must be sorted before using binary search.

C Program for Binary Search in Sorted Array

#include <stdio.h>

int main() {
    int n, i, search;
    int low, high, mid;
    int found = 0;
    
    // Ask user for number of elements
    printf("Enter the number of elements: ");
    scanf("%d", &n);
    
    // Declare array
    int arr[n];
    
    // Read sorted elements into the array
    printf("Enter %d sorted elements (ascending order):\n", n);
    for(i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    
    // Get element to search
    printf("\nEnter the element to search: ");
    scanf("%d", &search);
    
    // Binary search
    low = 0;
    high = n - 1;
    
    while(low <= high) {
        mid = (low + high) / 2;
        
        if(arr[mid] == search) {
            printf("\nElement %d found at position %d (index %d)\n", 
                   search, mid + 1, mid);
            found = 1;
            break;
        }
        else if(arr[mid] < search) {
            low = mid + 1;  // Search in right half
        }
        else {
            high = mid - 1;  // Search in left half
        }
    }
    
    // If element not found
    if(found == 0) {
        printf("\nElement %d not found in the array.\n", search);
    }
    
    return 0;
}

Sample Output

Enter the number of elements: 7
Enter 7 sorted elements (ascending order):
10 20 30 40 50 60 70

Enter the element to search: 50

Element 50 found at position 5 (index 4)

When Element is Not Found:

Enter the number of elements: 6
Enter 6 sorted elements (ascending order):
10 20 30 40 50 60

Enter the element to search: 100

Element 100 not found in the array.

Example with Even Number of Elements:

Enter the number of elements: 8
Enter 8 sorted elements (ascending order):
10 20 30 40 50 60 70 80

Enter the element to search: 30

Element 30 found at position 3 (index 2)

Program Explanation

Let's break down the code step by step:

Include Header File: #include <stdio.h> includes the standard input/output library.
Declare Variables:
- int n; — number of elements
- int i; — loop counter
- int search; — element to search for
- int low, high, mid; — pointers for binary search
- int found = 0; — flag (0 = not found, 1 = found)
Get User Input: Reads the sorted array elements from the user.
Get Search Element: Asks the user for the element to search.
Binary Search:
- Initialize: low = 0, high = n - 1
- While low <= high:
  - Calculate mid = (low + high) / 2
  - If arr[mid] == search, element found!
  - If arr[mid] < search, search in right half: low = mid + 1
  - If arr[mid] > search, search in left half: high = mid - 1
Handle Not Found: If found == 0, prints "Element not found".
Return: return 0; indicates successful program execution.

📝 Note: Binary search requires the array to be sorted in ascending order. If the array is in descending order, modify the comparison logic accordingly.

Binary Search Algorithm

Step-by-step algorithm:

Start
Read the sorted array elements
Read the element to search (target)
Set low = 0, high = n - 1
While low <= high:
- Set mid = (low + high) / 2
- If arr[mid] == target:
  - Print "Element found at position"
  - Set found = 1
  - Break the loop
- Else If arr[mid] < target:
  - Set low = mid + 1
- Else:
  - Set high = mid - 1
If found == 0:
- Print "Element not found"
End

Visual Example

Searching for 50 in the array [10, 20, 30, 40, 50, 60, 70]:

Step 1: low = 0, high = 6, mid = 3

Check arr[3] = 40 → 40 < 50, so search right half

Step 2: low = 4, high = 6, mid = 5

Check arr[5] = 60 → 60 > 50, so search left half

Step 3: low = 4, high = 4, mid = 4

Check arr[4] = 50 → Match found!

Result: Element found at position 5 (index 4)

Recursive Binary Search

Binary search can also be implemented recursively for a cleaner, more elegant solution:

#include <stdio.h>

int binarySearch(int arr[], int low, int high, int search) {
    if(low <= high) {
        int mid = (low + high) / 2;
        
        if(arr[mid] == search) {
            return mid;  // Element found
        }
        else if(arr[mid] < search) {
            return binarySearch(arr, mid + 1, high, search);  // Search right half
        }
        else {
            return binarySearch(arr, low, mid - 1, search);  // Search left half
        }
    }
    return -1;  // Element not found
}

int main() {
    int n, i, search, result;
    
    printf("Enter the number of elements: ");
    scanf("%d", &n);
    
    int arr[n];
    
    printf("Enter %d sorted elements (ascending order):\n", n);
    for(i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    
    printf("\nEnter the element to search: ");
    scanf("%d", &search);
    
    result = binarySearch(arr, 0, n - 1, search);
    
    if(result != -1) {
        printf("\nElement %d found at position %d (index %d)\n", 
               search, result + 1, result);
    } else {
        printf("\nElement %d not found in the array.\n", search);
    }
    
    return 0;
}

Time and Space Complexity

Scenario	Time Complexity
Best Case (Element at middle)	O(1)
Worst Case (Element not found)	O(log n)
Average Case	O(log n)
Space Complexity (Iterative)	O(1)
Space Complexity (Recursive)	O(log n)

Linear Search vs Binary Search

Feature	Linear Search	Binary Search
Array Requirement	Sorted or Unsorted	Sorted
Time Complexity	O(n)	O(log n)
Speed	Slow for large arrays	Fast for large arrays
Implementation	Simple	Moderate
Use Case	Small or unsorted arrays	Large sorted arrays

💻 Practice Exercise

Challenge 1: Modify the binary search program to search for the first occurrence of an element in a sorted array with duplicates.

Challenge 2: Implement binary search for an array sorted in descending order.

🔍 Click to Show Solution for Challenge 1

#include <stdio.h>

int main() {
    int n, i, search;
    int low, high, mid;
    int result = -1;
    
    printf("Enter the number of elements: ");
    scanf("%d", &n);
    
    int arr[n];
    
    printf("Enter %d sorted elements (ascending order):\n", n);
    for(i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    
    printf("\nEnter the element to search: ");
    scanf("%d", &search);
    
    // Binary search for first occurrence
    low = 0;
    high = n - 1;
    
    while(low <= high) {
        mid = (low + high) / 2;
        
        if(arr[mid] == search) {
            result = mid;
            high = mid - 1;  // Continue searching in left half
        }
        else if(arr[mid] < search) {
            low = mid + 1;
        }
        else {
            high = mid - 1;
        }
    }
    
    if(result != -1) {
        printf("\nFirst occurrence of %d found at position %d (index %d)\n", 
               search, result + 1, result);
    } else {
        printf("\nElement %d not found in the array.\n", search);
    }
    
    return 0;
}

Frequently Asked Questions

1. What is binary search in C?

Binary search is a fast searching algorithm that works on sorted arrays. It repeatedly divides the search interval in half until the target element is found or the interval becomes empty.

2. What is the time complexity of binary search?

The time complexity of binary search is O(log n), where n is the number of elements. This is much faster than linear search's O(n).

3. Does binary search work on unsorted arrays?

No, binary search requires a sorted array. If the array is unsorted, you must sort it first or use linear search.

4. What is the difference between iterative and recursive binary search?

Iterative binary search uses a loop and has O(1) space complexity. Recursive binary search uses function calls and has O(log n) space complexity due to the call stack.

5. Can binary search find the first occurrence of a duplicate element?

Yes, by modifying the algorithm to continue searching in the left half even after finding a match, you can find the first occurrence of a duplicate element.

💡 Tip: Binary search is one of the most important algorithms in computer science. Mastering it is essential for technical interviews and efficient programming.

Previous Topic: -->> Linear Search in Array || Next topic: -->> Find Second Largest Element

📚 Explore More Topics