# DSA: Binary Search

##### What is Searching?

Searching is a fundamental process in computer science that is commonly used to locate certain items or values within a data structure. Depending on the qualities of the data and the specific requirements of the search, different data formats and algorithms are used for searching.

##### What is Binary Search in DSA?

Binary search is an efficient searching algorithm specifically designed for sorted arrays or lists. It takes advantage of the fact that the array is sorted to reduce the search space in each iteration.

Conditions to be met before using Binary Search:

• The data structure must be sorted.
• Access to any element of the data structure takes constant time.
##### Algorithm:

The binary search algorithm follows these steps:

1. Compare the target value with the middle element of the array.
2. If they are equal, the search is successful, and the index of the target value is returned.
3. If the target value is less than the middle element, the search continues in the left half of the array.
4. If the target value is greater than the middle element, the search continues in the right half of the array.
5. Repeat steps 1-4 until the target value is found or the search interval becomes empty

Note: Binary search effectively removes half of the remaining entries by dividing the search interval in half at each step, resulting in a substantially faster search than linear search.

##### Binary Seach Usage:
1. Large dataset: Binary search is ideal for searching in large datasets because of its efficient time complexity of O(log n).
2. Sorted dataset: Binary search requires the dataset to be sorted in ascending or descending order. It leverages the sorted nature of the data to repeatedly divide the search space in half, efficiently narrowing down the possible locations of the target value.
3. Contiguous memory: Random access to elements in contiguous memory allows for efficient access to midpoints during each iteration of the search process.
4. Simple data structure: Binary search works best with simple data structures that do not have complex relationships or dependencies.
##### Implementation of Binary Search in Java:
``````public class BinarySearch {
public static int binarySearch(int[] arr, int target) {
int low = 0;
int high = arr.length - 1;

while (low <= high) {
int mid = (low + high) / 2;

if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}

}

public static void main(String[] args) {
int[] arr = {2, 4, 6, 8, 10, 12, 14};
int target = 10;
int result = binarySearch(arr, target);

if (result == -1) {
} else {
System.out.println("Element found at index " + result);
}
}
}
``````

In the given code:

1. The `binarySearch` method takes an array `arr` and a target value `target` as parameters and returns the index of the target value in the array or -1 if it is not found.
2. It initializes two variables, `low` and `high`, to keep track of the search range.
3. The `while` loop continues as long as `low` is less than or equal to `high`, indicating that elements are remaining to be searched.
4. Inside the loop, the midpoint `mid` is calculated as the average of `low` and `high`.
5. If the target value is found at the midpoint `arr[mid]`, the method returns `mid`.
6. If the target value is less than `arr[mid]`, the search is narrowed down to the left half of the remaining range by updating `high` to `mid - 1`.
7. If the target value is greater than `arr[mid]`, the search is narrowed down to the right half of the remaining range by updating `low` to `mid + 1`.
8. If the loop finishes without finding the target value, the method returns -1 to indicate that the target value is not present in the array.
9. In the `main` method, we create an example array, `arr`, and a target value, `target`, to search for.
10. We call the `binarySearch` method and print the result based on whether the target value was found or not.
##### Problems based on Binary Search:

Given an array Arr[] of size L and a number N, you need to write a program to find if there exists a pair of elements in the array whose difference is N.

Example:

```Input:
L = 6, N = 78
arr[] = {5, 20, 3, 2, 5, 80}
Output: 1
Explanation: (2, 80) have difference of 78.```
``````class Solution
{
public boolean findPair(int arr[], int size, int n)
{
Arrays.sort(arr); // Sort the array in ascending order

for (int i = 0; i < arr.length; i++) {
int target = arr[i] + n;
int index = binarySearch(arr, target, i + 1, arr.length - 1);

if (index != -1) {
return true; // Pair found
}
}

}

public static int binarySearch(int[] arr, int target, int low, int high) {
while (low <= high) {
int mid = low + (high - low) / 2;

if (arr[mid] == target) {
return mid; // Target found
} else if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}

}

}``````

Time Complexity:

1. Sorting: The code uses `Arrays.sort(arr)` to sort the array with time complexity of O(N log N), where N is the size of the array.
2. Binary Search: The time complexity of binary search is O(log N), where N is the size of the array. Since this binary search is performed for each element, the overall time complexity of the binary search part is O(N log N).
3. Overall: The dominant factor in the time complexity is the sorting step, which is O(N log N). Therefore, the overall time complexity of the code is O(N log N).

Space Complexity: Considering the sorting step as the dominant factor, the overall space complexity of the code is O(N).

Given two arrays: a1[0..n-1] of size n and a2[0..m-1] of size m. Task is to check whether a2[] is a subset of a1[] or not. Both the arrays can be sorted or unsorted. There can be duplicate elements.

Example:

```Input:
a1[] = {11, 7, 1, 13, 21, 3, 7, 3}
a2[] = {11, 3, 7, 1, 7}
Output:
Yes
Explanation:
a2[] is a subset of a1[]```
``````class Compute {
public String isSubset( long a1[], long a2[], long n, long m) {
//small array

Arrays.sort(a1); // Sort the first array

for (int i = 0; i < m; i++) {
if (binarySearch(a1, a2[i]) == -1) {
}
}

return "Yes"; // All elements of a2[] found in a1[]
}

public int binarySearch(long[] arr, long target) {
int low = 0;
int high = arr.length - 1;

while (low <= high) {
int mid = (low + high) / 2;

if (arr[mid] == target) {
return mid; // Target found
} else if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}

}
}``````

Time Complexity: overall time complexity of the code is O(N log N + M log N), where N & M is the size of arr1[] & arr2[].

Space Complexity: O(N)

In this code:

1. The `isSubset` method takes two long arrays (`a1[]` and `a2[]`) and their respective sizes (`n` and `m`) as parameters.
2. The first array, `a1[]`, is sorted using `Arrays.sort(a1)` to enable binary search.
3. The `for` loop iterates over each element in `a2[]` and checks if it is found in `a1[]` using the `binarySearch` method.
4. The `binarySearch` method performs binary search in the sorted array, `arr[]`, and returns the index of the target if found or -1 if not found.
5. If any element from `a2[]` is not found in `a1[]`, the method returns `"No"`, indicating that `a2[]` is not a subset of `a1[]`.
6. If all elements from `a2[]` are found in `a1[]`, the method returns `"Yes"`, indicating that `a2[]` is a subset of `a1[]`.