Binary Search In Java

Binary search is an efficient algorithm used to locate a specific value within a sorted collection of elements. It follows a divide-and-conquer strategy to narrow down the search range by repeatedly dividing it in half.

Algorithm

1. Preparation: Start with a sorted collection of elements, such as an array. For binary search to work correctly, the elements must be sorted in ascending or descending order.

2. Initialization: Set the lower and upper bounds of the search range. Initially, the lower bound is the first element of the collection, and the upper bound is the last element.

3. Search: Calculate the middle element of the current range. If the middle element is equal to the desired value, the search is successful, and the algorithm can return the index or element found.

4. Comparison: If the middle element is greater than the desired value, it means the value, if present, must be in the lower half of the range. Update the upper bound to be one position before the middle element.

5. Comparison: If the middle element is less than the desired value, it means the value, if present, must be in the upper half of the range. Update the lower bound to be one position after the middle element.

6. Repeat: Repeat steps 3-5 until the search range becomes empty, meaning the lower bound is greater than the upper bound. In this case, the value is not present in the collection, and the algorithm terminates.

Example

Suppose we have a sorted array of numbers: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91].

We want to find the index of the element 23 in this array using binary search.

1. Preparation: We have a sorted array: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91].

2. Initialization: We set the lower bound (l) to 0 (the index of the first element) and the upper bound (u) to 9 (the index of the last element).

3. Search: We calculate the middle index (m) as (l + u) / 2 = (0 + 9) / 2 = 4. The middle element is 16.

4. Comparison: Since the middle element (16) is less than the desired value (23), we update the lower bound (l) to m + 1, which is 5.

5. Comparison: We recalculate the middle index (m) as (l + u) / 2 = (5 + 9) / 2 = 7. The middle element is 56.

6. Comparison: Since the middle element (56) is greater than the desired value (23), we update the upper bound (u) to m - 1, which is 6.

7. Repeat: We recalculate the middle index (m) as (l + u) / 2 = (5 + 6) / 2 = 5. The middle element is 23.

Since the middle element (23) is equal to the desired value, the search is successful. The index of 23 in the array is 5.

Binary search reduces the search range by half in each iteration, resulting in a time complexity of O(log n), where n is the number of elements in the collection. This makes it significantly faster than linear search algorithms, especially for large collections.

However, it's important to note that binary search requires the collection to be sorted beforehand. If the collection is unsorted, binary search cannot be applied, and alternative algorithms like linear search or sorting algorithms should be considered.

Click here to read about linear search

Code

import java.util.Arrays;

public class Search {

    public static void main(String[] args) {
        int arr[] = {1,2,3,4,5,6,6,7,12,13,14,15,15,15,18,19};
        System.out.println("my reusult : " + binarySearch(arr, 19));

        //Binary search using predefined method of java.util.Arrays class
        System.out.println("Arrays.binarySearch() : "+ Arrays.binarySearch(arr, 19));
    }

    //Binary Search
    public static int binarySearch(int [] arr, int numberToFind){
        return checkMidIndex(arr, 0, arr.length-1, numberToFind );        
    }

    private static int checkMidIndex(int[] arr, int low, int high, int numberToFind) {
        if(low>high)
            return -1;
        else {
            int midIndex = low + (high-low)/2;

            if(arr[midIndex] == numberToFind)
                return midIndex;
            else if (arr[midIndex] > numberToFind) 
                return checkMidIndex(arr, 0, midIndex-1, numberToFind);
            else
                return checkMidIndex(arr, midIndex+1, high, numberToFind);        
        }
    }

}

Output

my reusult : 15

Arrays.binarySearch() : 15