In the previous article , we learnt about the searching algorithms and two types of searching algorithms. We learnt about** Linear Search algorithm**. In this article, we will learn about another important searching algorithm called

**.**

*Binary Search algorithm*## About Binary Search Algorithm

Binary search is an efficient algorithm designed to locate a specific value within a sorted array or list. It achieves this by continuously dividing the search range in half until the target value is either found or determined to be absent.

Here’s how the binary search algorithm works:

**Input**: Start with a sorted array or list of elements and a target value to search for.**Initialization**: Define two pointers,`left`

and`right`

, which point to the first and last elements of the array, respectively.- Search Process:
- At each iteration, calculate the midpoint of the current segment (using
`mid = (left + right) / 2`

or`mid = (left + right) >> 1`

). - Compare the middle element with the target value.
- If they match, return the index of the middle element, indicating the search is successful.
- If the target is smaller than the middle element, adjust the
`right`

pointer to`mid - 1`

, reducing the search space to the left half. - If the target is larger than the middle element, move the
`left`

pointer to`mid + 1`

, reducing the search space to the right half.

**Repeat**the search steps until the target is found or the pointers cross, indicating the target is not present in the array.

### Problem Statement-Binary Search Algorithm

Given a sorted array `arr`

of size `N`

and a target element, the task is to determine the position of the target element in the array. If the element is not present, the function should return a result indicating that.

##### Here’s a java code of binary search algorithm(Iterative code):

```
public class BinarySearch {
// Iterative method for binary search
static int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
// Check if target is at mid
if (arr[mid] == target)
return mid;
// If target is larger, disregard left half
if (arr[mid] < target)
left = mid + 1;
// If target is smaller, disregard right half
else
right = mid - 1;
}
// If target is not in the array
return -1;
}
public static void main(String[] args) {
int[] arr = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
int target = 23;
int result = binarySearch(arr, target);
if (result == -1)
System.out.println("Element not found in array");
else
System.out.println("Element found at index " + result);
}
}
```

##### Recursive Approach for Binary Search Algorithm:

```
public class BinarySearch {
// Recursive method for binary search
static int binarySearch(int[] arr, int target, int left, int right) {
if (left <= right) {
int mid = left + (right - left) / 2;
// Check if target is at mid
if (arr[mid] == target)
return mid;
// If target is smaller, search left subarray
if (arr[mid] > target)
return binarySearch(arr, target, left, mid - 1);
// Otherwise, search right subarray
return binarySearch(arr, target, mid + 1, right);
}
// Target is not in the array
return -1;
}
public static void main(String[] args) {
int[] arr = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
int target = 23;
int result = binarySearch(arr, target, 0, arr.length - 1);
if (result == -1)
System.out.println("Element not found in array");
else
System.out.println("Element found at index " + result);
}
}
```

The key advantage of binary search is its efficiency. With each comparison, binary search halves the size of the search space, making it particularly useful for large datasets.

##### Complexity of Binary Search Algorithm:

- Time-Complexity: O(logn)
- Space-Complexity: O(1)

The logarithmic time complexity means that binary search can efficiently handle even massive datasets.