Search

# 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:

Space complexity: O(1) in case of iterative and O(logn) for recursion.

Follow for more tech blogs #programmersdoor #searching #datastructures