Home > Java > javaTutorial > body text

How to implement binary search algorithm using java

WBOY
Release: 2023-09-19 12:57:41
Original
795 people have browsed it

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; //表示未找到目标元素
    }
}
Copy after login

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("未找到目标元素");
        }
    }
}
Copy after login

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!

Related labels:
source:php.cn
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template
About us Disclaimer Sitemap
php.cn:Public welfare online PHP training,Help PHP learners grow quickly!