Binary Search is an efficient searching algorithm used to find an element in a sorted array.
It follows a divide-and-conquer approach, which means it repeatedly divides the search space in half until the element is found or the search space is empty.
🔹 How Binary Search Works?
- The algorithm starts by checking the middle element of the array.
- If the middle element matches the key, return the index.
- If the key is smaller than the middle element, search in the left half.
- If the key is greater, search in the right half.
- Repeat the process until the key is found or the array is completely searched.
🔹 Time Complexity of Binary Search
✅ Best Case (O(1)) → When the key is at the middle position.
✅ Worst Case (O(log n)) → When the key is at the end or not present.
✅ Average Case (O(log n)) → The search space is reduced by half in each step.
📌 Binary Search in C (Dynamic Memory Allocation)
#include <stdio.h>
#include <stdlib.h> // For malloc() and free()
// Function for Binary Search (Iterative)
int binarySearch(int *arr, int size, int key) {
int left = 0, right = size - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == key) {
return mid; // Element found, return index
} else if (arr[mid] < key) {
left = mid + 1; // Search in the right half
} else {
right = mid - 1; // Search in the left half
}
}
return -1; // Element not found
}
int main() {
int n, key, result;
// Get array size from user
printf("Enter the number of elements: ");
scanf("%d", &n);
// Dynamic Memory Allocation for array
int *arr = (int *)malloc(n * sizeof(int));
// Checking if memory allocation is successful
if (arr == NULL) {
printf("Memory allocation failed!\n");
return 1;
}
// Getting sorted array elements from user
printf("Enter %d sorted elements: ", n);
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
// Get the key to search
printf("Enter the element to search: ");
scanf("%d", &key);
// Call binarySearch function
result = binarySearch(arr, n, key);
// Print the result
if (result != -1) {
printf("Element found at index %d\n", result);
} else {
printf("Element not found!\n");
}
// Free allocated memory
free(arr);
return 0;
}
📌 Line-by-Line Explanation (English)
1️⃣ Header Files
#include <stdio.h>
#include <stdlib.h> // For malloc() and free()
✅ stdio.h → Used for input-output functions (printf, scanf).
✅ stdlib.h → Used for dynamic memory allocation (malloc, free).
2️⃣ Function for Binary Search
int binarySearch(int *arr, int size, int key) {
int left = 0, right = size - 1;
📌 binarySearch function takes a pointer arr, the size of the array, and the key to search as inputs.
📌 left = 0 → Represents the first index.
📌 right = size - 1 → Represents the last index.
while (left <= right) {
int mid = left + (right - left) / 2;
📌 The loop runs until left is less than or equal to right.
📌 mid = left + (right - left) / 2 → Finds the middle index to avoid overflow.
if (arr[mid] == key) {
return mid; // Element found, return index
} else if (arr[mid] < key) {
left = mid + 1; // Search in the right half
} else {
right = mid - 1; // Search in the left half
}
}
return -1; // Element not found
}
📌 If arr[mid] == key, return mid (index where the key is found).
📌 If arr[mid] < key, search on the right half (left = mid + 1).
📌 If arr[mid] > key, search on the left half (right = mid - 1).
📌 If the element is not found, return -1.
3️⃣ Taking Input from the User
printf("Enter the number of elements: ");
scanf("%d", &n);
📌 User enters the size of the array (n).
4️⃣ Allocating Memory Dynamically
int *arr = (int *)malloc(n * sizeof(int));
📌 malloc(n * sizeof(int)) → Allocates memory for n integers dynamically.
📌 arr is a pointer that stores the address of allocated memory.
5️⃣ Checking if Memory Allocation was Successful
if (arr == NULL) {
printf("Memory allocation failed!\n");
return 1;
}
📌 If malloc fails to allocate memory, arr will be NULL.
📌 If allocation fails, an error message is displayed, and the program exits.
6️⃣ Taking Sorted Array Elements from the User
printf("Enter %d sorted elements: ", n);
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
📌 A for loop is used to take n sorted elements as input from the user.
7️⃣ Taking the Key to Search from the User
printf("Enter the element to search: ");
scanf("%d", &key);
📌 User enters the key (the value to search for).
8️⃣ Calling the Binary Search Function
result = binarySearch(arr, n, key);
📌 Calls the binarySearch() function and stores the returned value in result.
9️⃣ Checking the Search Result
if (result != -1) {
printf("Element found at index %d\n", result);
} else {
printf("Element not found!\n");
}
📌 If result != -1, it means the element is found, and the index is printed.
📌 If result == -1, it means the element is not found, and an appropriate message is displayed.
🔟 Freeing the Allocated Memory
free(arr);
📌 Since we allocated memory dynamically using malloc(), we must free it after use to avoid memory leaks.
📌 Example Output
Enter the number of elements: 5
Enter 5 sorted elements: 10 20 30 40 50
Enter the element to search: 30
Element found at index 2
📌 Key Takeaways
✅ Binary Search is a faster searching algorithm than linear search.
✅ Time Complexity → Worst case O(log n), Best case O(1).
✅ Requires Sorted Array → Binary search works only on sorted data.
✅ Dynamic Memory Allocation → malloc() is used to allocate memory dynamically.
✅ Memory Management → free(arr) is used to release allocated memory.
🎯 Do you understand the explanation? Let me know if you need more details!
0 Comments