# Binary Search

It is search algorithm that finds value within the sorted array. It compares the target value to the middle element of array. If they are not equal than, the half in which the target cannot lie is eliminated and the search continues on the remaining half, again repeating the same process until the target value is found. If the search ends with the remaining half being empty, the target is not in the array. Example: array[]={2, 5, 8, 10, 16, 23, 39, 56, 72, 95} key is 23 L=0 1 2 3 M=4 5 6 7 8 H=9 2 5 8 10 16 23 39 56 72 95 Now as 23>16 take 2nd half 0 1 2 3 4 L=5 6 M=7 8 H=9 2 5 8 10 16 23 39 56 72 95 Now as 23<56 take 1st half 0 1 2 3 4 L=5,M=5 H=6 7 8 H=9 2 5 8 10 16 23 39 56 72 95 Implementation using C: (Recursion) #include <stdio.h>

int binary_Search(int arr[], int l, int r, int x)

{

if (r >= l) {

int mid = l + (r - l) / 2;

// If the element is present at the middle

if (arr[mid] == x)

return mid;

// If element is smaller than mid, then

// it can only be present in left subarray

if (arr[mid] > x)

return binary_Search(arr, l, mid - 1, x);

//else element can only be present in right subarray

return binary_Search(arr, mid + 1, r, x);

}

// when element is not present in array

return -1;

}

int main(void)

{

int arr[] = { 20, 30, 40, 100, 400 };

int n = sizeof(arr) / sizeof(arr[0]);

int x = 100;

int result = binary_Search(arr, 0, n - 1, x);

(result == -1) ? printf("Element is not present in array")

: printf("Element is present at index %d",

result);

return 0;

} Output:

Element is present at index 3 (Iterative) #include <stdio.h>

int binary_Search(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;

}

// element was

// not present

return -1;

}

int main(void)

{

int arr[] = { 20, 30, 40, 100, 400 };

int n = sizeof(arr) / sizeof(arr[0]);

int x = 100;

int result = binary_Search(arr, 0, n - 1, x);

(result == -1) ? printf("Element is not present"

" in array")

: printf("Element is present at "

"index %d",

result);

return 0;

} Output:

Element is present at index 3 Miscellaneous: Time Complexity for best case: O(1) . For more click here. Space complexity: O(1) in case of iterative and O(logn) for recursion. Follow for more tech blogs #programmersdoor #searching #datastructures