Project 2
Binary Search is a searching algorithm used in a sorted array by repeatedly dividing the search interval in half. The idea of binary search is to use the information that the array is sorted and reduce the time complexity to O(Log n).
Binary Search Algorithm: The basic steps to perform Binary Search are:
- Sort the array in ascending order.
- Set the low index to the first element of the array and the high index to the last element.
- Set the middle index to the average of the low and high indices.
- If the element at the middle index is the target element, return the middle index.
- If the target element is less than the element at the middle index, set the high index to the middle index – 1.
- If the target element is greater than the element at the middle index, set the low index to the middle index + 1.
- Repeat steps 3-6 until the element is found or it is clear that the element is not present in the array.
// C program to implement iterative Binary Search#include <stdio.h>// A iterative binary search function. It returns// location of x in given array arr[l..r] if present,// otherwise -1int binarySearch(int arr[], int l, int r, int x){ while (l <= r) { int m = l + (r - l) / 2; // Check if x is present at mid if (arr[m] == x) return m; // If x greater, ignore left half if (arr[m] < x) l = m + 1; // If x is smaller, ignore right half else r = m - 1; } // if we reach here, then element was // not present return -1;}int main(void){ int arr[] = { 2, 3, 4, 10, 40 }; int n = sizeof(arr) / sizeof(arr[0]); int x = 10; int result = binarySearch(arr, 0, n - 1, x); (result == -1) ? printf("Element is not present" " in array") : printf("Element is present at " "index %d", result); return 0;}