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.

Time & Space complexity:

Operation	Time Complexity	Space Complexity
Binary Search	O(log N), where N is no. of elements	O(1)
Comparison	O(1)	O(1)

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;
            }
        }

        return -1; // Target element not found
    }

    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) {
            System.out.println("Element not found");
        } 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
            }
        }
        
        return false; // Pair not 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;
            }
        }
        
        return -1; // Target not found
    }
    
}

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 "No"; // Element not found in a1[]
        }
    }

    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;
        }
    }

    return -1; // Target not found
}
}

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[].

Note: also read about DSA: Types of Tree

Follow Me

If you like my post please follow me to read my latest post on programming and technology.

https://www.instagram.com/coderz.py/

https://www.facebook.com/coderz.py