Illustration of the principle and implementation of Java classic algorithm binary search

This article brings you relevant knowledge about java. The half search method is also called binary search. As the name suggests, it divides the data into two halves and then determines which half the key is looking for. , and then repeat the above steps until the target key is found. Let’s take a look at it. I hope it will be helpful to everyone.

Recommended study: "java video tutorial"

Binary search

Binary search is also called half search ( Binary Search), which is a more efficient search method that can complete the search within logarithmic time complexity of the data scale. It is a search algorithm for finding a specific element in an ordered array.

Algorithm idea

Taking the ascending sequence as an example, compare the size of the target element and the element in the middle of the sequence. If the target element is larger than the element in the middle, continue in the second half of the sequence. Perform a binary search in; if the target element is smaller than the element in the middle position, compare the first half of the array; if they are equal, the position of the element is found. The length of the array for each comparison will be half of the previous array until the position of equal elements is found or the target element is not found.

Illustration

Given an ordered array in ascending order nums=[-1, 0, 2, 5, 8, 12, 18, 38, 43, 46]

Then find the target value target = 12 in the array.

The diagram is as follows:

##利强综合的链接

Portal

Title description:

Given an n-element ordered (ascending) integer array nums and a target value target, write a function to search the target in nums. If the target value exists, return the subscript, otherwise return -1.

Example 1:

Input: nums = [-1,0,3,5,9,12], target = 9

Output: 4
Explanation : 9 appears in nums and the subscript is 4

Example 2:

Input: nums = [-1,0,3,5,9,12] , target = 2

Output: -1
Explanation: 2 does not exist in nums, so it returns -1

Solution idea:

According to the meaning of the question, we get the The array is an ordered array, which is also a prerequisite for using binary search.

Define two pointers pointing to the first and last elements of the array respectively;
• Find the middle value mid of the array;
• If
• nums[mid] < ; target, then the target is in the second half of the array, otherwise nums[mid] > target is in the first half;
Repeat the previous step until
• nums[ mid] = target, indicating that the target is found and the subscript is returned.

Java code implementation:

class Solution {
    public int search(int[] nums, int target) {
        int left = 0,right = nums.length - 1;
        while(left <= right) { // 循环条件
            int mid = left + (right - left) / 2;
            if(nums[mid] == target){
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;  // 找不到则返回-1
    }
}

Complexity analysis:

Time complexity: O(logn), where n is the length of the array.
• Space complexity: O(1).

Recommended study: "

java video tutorial"

The above is the detailed content of Illustration of the principle and implementation of Java classic algorithm binary search. For more information, please follow other related articles on the PHP Chinese website!