# 1. Introduction

*Binary Search* is a divide-and-conquer search algorithm that works on a sorted array or list. It finds the position of a target value by comparing the target value to the middle element of the array. If they are not equal, the half in which the target cannot lie is eliminated, and the search continues on the remaining half.

# 2. Program Steps

1. Initialize two pointers: *low* at position 0 and *high* at the last position of the array.

2. Calculate the middle index: *mid = (low + high) / 2*.

3. Compare the element at the middle index with the target value.

4. If they are equal, return the *mid* index.

5. If the target is larger than the middle element, update *low* to *mid + 1* and repeat from step 2.

6. If the target is smaller than the middle element, update *high* to *mid – 1* and repeat from step 2.

7. If the value isn’t present in the array, return *-1*.

# 3. Code Program

```
public class BinarySearch {
// Binary search method
static int binarySearch(int arr[], int x) {
int low = 0, high = arr.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
// Check if x is present at mid
if (arr[mid] == x)
return mid;
// If x is greater, ignore the left half
if (arr[mid] < x)
low = mid + 1;
// If x is smaller, ignore the right half
else
high = mid - 1;
}
// if we reach here, then the element was not present
return -1;
}
// Driver method
public static void main(String args[]) {
int arr[] = {2, 3, 4, 10, 40};
int x = 10;
int result = binarySearch(arr, x);
if (result == -1)
System.out.println("Element not present in the array");
else
System.out.println("Element found at index: " + result);
}
}
```

### Output:

Element found at index: 3

# 4. Step By Step Explanation

1. *BinarySearch*: This is the main class that contains methods for performing binary search on an array.

2. *binarySearch(int arr[], int x)*: This is the method that implements the binary search algorithm. It takes in an array *arr* and a target value *x* to search for.

3. Within the *binarySearch* method, the middle index of the current search range is computed as *mid = (low + high) / 2*.

4. The element at *mid* is compared to the target *x*. If they match, *mid* is returned indicating the position of the target in the array.

5. If the target is greater than the middle element, the *low* pointer is moved one position past *mid* to search the right half.

6. If the target is less than the middle element, the *high* pointer is moved one position before *mid* to search the left half.

7. The search continues until *low* exceeds *high* or the target is found.

8. In the *main* method, an array is defined, the target value is set, and the binary search method is called. The result is then printed.

By dividing the search range in half with every step, *Binary Search* achieves a time complexity of O(log n), making it much faster than linear search for large datasets.