Binary search is an efficient algorithm for finding a specific value in a sorted array. 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; otherwise, it continues in the upper half. This method drastically reduces the number of comparisons needed to find the target value, making it much faster than linear search for large datasets.<\/p>\n\n\n
\n#include <stdio.h>\n\nint binarySearch(int arr[], int size, int target) {\n int left = 0;\n int right = size - 1;\n\n while (left <= right) {\n int mid = left + (right - left) \/ 2;\n\n \/\/ Check if the target is present at mid\n if (arr[mid] == target) {\n return mid; \/\/ Return the index if found\n }\n \/\/ If target is greater, ignore the left half\n else if (arr[mid] < target) {\n left = mid + 1;\n }\n \/\/ If target is smaller, ignore the right half\n else {\n right = mid - 1;\n }\n }\n return -1; \/\/ Return -1 if not found\n}\n\nint main() {\n int arr[] = {1, 3, 5, 7, 9, 11, 13, 15};\n int size = sizeof(arr) \/ sizeof(arr[0]);\n int target;\n\n printf("Enter the number to search: ");\n scanf("%d", &target);\n\n int result = binarySearch(arr, size, target);\n\n if (result != -1) {\n printf("Element found at index: %d\\n", result);\n } else {\n printf("Element not found in the array.\\n");\n }\n\n return 0;\n}\n\n<\/pre><\/div>\n\n\nExplanation<\/h3>\n\n\n\n\n- Function Definition<\/strong>:\n
\nbinarySearch(int arr[], int size, int target)<\/code>: Takes a sorted array, its size, and the target value to search for.<\/li>\n<\/ul>\n<\/li>\n\n\n\n- Initialization<\/strong>:\n
\n- Two pointers,
left<\/code> and right<\/code>, are initialized to the start and end of the array, respectively.<\/li>\n<\/ul>\n<\/li>\n\n\n\n- Loop<\/strong>:\n
\n- A
while<\/code> loop runs as long as left<\/code> is less than or equal to right<\/code>.<\/li>\n\n\n\n- The middle index (
mid<\/code>) is calculated, and the target is compared with the value at mid<\/code>.<\/li>\n\n\n\n- Depending on the comparison:\n
\n- If the target equals
arr[mid]<\/code>, the index is returned.<\/li>\n\n\n\n- If the target is greater,
left<\/code> is updated to mid + 1<\/code>.<\/li>\n\n\n\n- If the target is smaller,
right<\/code> is updated to mid - 1<\/code>.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n\n\n\n- Return Values<\/strong>:\n
\n- Returns the index of the target if found.<\/li>\n\n\n\n
- Returns -1 if the target is not found.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
- Main Function<\/strong>:\n
\n- Initializes a sorted array and prompts user input for the target value.<\/li>\n\n\n\n
- Calls
binarySearch<\/code> and displays the result.<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n\n\n\nInput<\/h3>\n\n\n\n
When you run the program, it prompts the user to enter a number to search for. For example:<\/p>\n\n\n
\nEnter the number to search: 7\n\n<\/pre><\/div>\n\n\nOutput<\/h3>\n\n\n\n
The output will indicate whether the element was found and, if so, at which index:<\/p>\n\n\n
\nElement found at index: 3\n\n<\/pre><\/div>\n\n\nOr if the element is not found:<\/p>\n\n\n
\nElement not found in the array.\n\n<\/pre><\/div>\n\n\nConclusion<\/h3>\n\n\n\n
Binary search is a highly efficient algorithm for searching elements in a sorted array, with a time complexity of O(log n). This makes it significantly faster than linear search, especially for larger datasets. However, it is crucial that the array is sorted before applying binary search. Its effectiveness and efficiency make it a popular choice in many applications where fast search operations are required.<\/p>\n