How to implement binary search algorithm using java

How to use Java to implement the binary search algorithm

The binary search algorithm is an efficient search method suitable for sorted arrays. Its basic idea is to continuously narrow the search range, compare the search value with the elements in the middle of the array, and decide whether to continue searching the left half or the right half based on the comparison result until the target element is found or the search range is reduced to empty.

Let’s introduce in detail how to implement the binary search algorithm in Java.

Step 1: Implement the binary search method

public class BinarySearch {
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        
        while (left <= right) {
            int mid = (left + right) / 2;
            
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return -1; //表示未找到目标元素
    }
}

Step 2: Test the binary search method

public class Main {
    public static void main(String[] args) {
        int[] arr = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20}; //已排序数组
        int target = 12; //要查找的目标元素
        int index = BinarySearch.binarySearch(arr, target);
        
        if (index != -1) {
            System.out.println("目标元素在数组中的位置为：" + index);
        } else {
            System.out.println("未找到目标元素");
        }
    }
}

The above code first defines a BinarySearch class, in which Contains a static method binarySearch for implementing the binary search algorithm. In the binarySearch method, we define two pointers left and right to point to the leftmost and rightmost elements of the search range respectively. In a loop, the index of the middle element mid is calculated and then the lookup value is compared with arr[mid]. If the two are equal, it means that the target element is found and its index value mid is returned. If the search value is greater than arr[mid], move the left pointer one position to the right and narrow the search range to the right half. If the search value is less than arr[mid], move the right pointer one position to the left and narrow the search range to the left half. The loop continues until the target element is found or the search range is empty. If the target element is not found after the loop ends, -1 is returned to indicate that it was not found.

In the main method of the Main class, we create a sorted array arr and a target element to be found target. Then call the binarySearch method of the BinarySearch class to perform a binary search, and store the returned result in the index variable. Finally, it is judged whether the target element is found based on the returned result, and the corresponding result is printed.

Through the above code examples, we can see that implementing the binary search algorithm in Java is very simple and only requires a few lines of code to complete. This method has a search time complexity of O(logn), which is very efficient and suitable for large sorted arrays. If multiple search operations are required, the sorting operation of the array can be split separately to improve efficiency.

I hope this article will help you understand and use the binary search algorithm!

The above is the detailed content of How to implement binary search algorithm using java. For more information, please follow other related articles on the PHP Chinese website!