详解二分查找算法Binary Search

一、binarysearch怎么读

Binary Search是一种搜索算法，也称为折半搜索。Binary Search是计算机科学中的经典算法，用于在有序数组中查找某一特定元素的位置。

读音为 [ˈbaɪn ə ri sɜrtʃ]，中文通常称之为“二分查找”，“折半查找”或“二分法”，相信大家已经听过这些词汇了。

二、binary search方法只能操作

二分查找法只适用于元素有序的情况下，如果是无序的元素需要先进行排序操作，才能使用二分查找算法。

时间复杂度为O(logN)。与暴力搜索的时间复杂度O(N)相比，二分查找的时间复杂度更小，效率更高。

三、binarysearch()方法的作用

/**
 * Searches the specified array for the specified value using the binary search algorithm.
 * @param  arr   the array to be searched
 * @param  key   the value to be searched for
 * @return       index of the search key, if it is contained in the array;
 *               otherwise, (-(insertion point) - 1). 
 *               The insertion point is defined as the point at which the key would be 
 *               inserted into the array: the index of the first element greater than the key, 
 *               or arr.length if all elements in the array are less than the specified key.
 */
public static int binarySearch(int[] arr, int key) {
    int low = 0;
    int high = arr.length - 1;
    while (low >> 1;
        int midVal = arr[mid];
        if (midVal  key)
            high = mid - 1;
        else
            return mid; // key found
    }
    return -(low + 1);  // key not found.
}

binarySearch()方法是二分查找算法在Java数组中经典的实现方法。该方法接收一个已经排好序的数组，和需要查找的值，并返回值在数组中的索引位置。如果值不存在于数组中，则返回插入值的索引（可以认为是不存在值的位置）。

四、binarysearch的例子

public static void main(String[] args) {
    int[] nums = {1, 3, 5, 6, 8, 9};
    int target = 6;
    int index = binarySearch(nums, target);
    System.out.println("Index of " + target + " is " + index);
}

上述例子中，我们定义了一个数组nums和一个需要查找的值target，然后调用binarySearch()方法查找target的位置。最终结果显示target在nums中的索引位置为3。

五、binary search读法

Binary Search的中文翻译为“二分查找”，整个过程就是不断地将数组中间位置的值与目标值进行比较。如果中间位置的值大于目标值，则在数组的左半部分查找，反之则在右半部分查找，直到找到目标值为止。

在英文中，Binary Search的发音是[“ˈbaɪnərɪsɜrtʃ”]，其中Binary的“bi”读为“baɪ”，Search的“sea”读为“sɜrʧ”。

六、binary search方法的作用

Binary search是一种高效的查找算法，常用于处理大数据量的查找操作。二分查找法的时间复杂度为O(logN)，比暴力查找的时间复杂度O(N)效率更高。

在Java中，Arrays类提供了binarySearch()方法，可以方便地对数组进行二分查找操作，应用广泛。

七、arrays binarysearch

public static void main(String[] args) {
    int[] nums = {1, 3, 5, 6, 8, 9};
    int target = 6;
    int index = Arrays.binarySearch(nums, target);
    System.out.println("Index of " + target + " is " + index);
}

Java中的Arrays类提供了binarySearch()方法，可以快速地查找一个已经排好序的数组中的某个值。

八、binarysearch方法

在Java中，Collections类也提供了binarySearch()方法，可以对已经实现了Comparable接口的对象进行二分查找。

public static void main(String[] args) {
    List nums = new ArrayList();
    nums.add(1);
    nums.add(3);
    nums.add(5);
    nums.add(6);
    nums.add(8);
    nums.add(9);
    int target = 3;
    int index = Collections.binarySearch(nums, target);
    System.out.println("Index of " + target + " is " + index);
}

九、binarysearch算法

二分查找算法是一种经典的分治思想的应用，它的基本思路是将一个有序数组不断地二分，来查找目标元素。由于其时间复杂度非常低，所以被广泛地应用于各种领域中。

以下是二分查找的经典算法实现：

public static int binarySearch(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
    while (left  target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
}

上述代码中，我们首先将sortedArray数组的左右边界设为0和数组长度-1，然后在while循环中不断缩小左右边界的范围，直到找到目标元素或者发现没有这个元素为止，最后返回查找结果。

原创文章，作者：OFCJN，如若转载，请注明出处：https://www.506064.com/n/325059.html