前言

二分查找算法，也称折半搜索算法、对数搜索算法，是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；

如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

二分查找的思想是利用数组排序的信息，将时间复杂度降低到 O(Log n)。

案例：

1. 将 x 与中间元素进行比较。
2. 如果 x 与中间元素匹配，我们返回中间索引。
3. Else 如果 x 大于中间元素，则 x 只能位于中间元素之后的右半子数组中。所以我们重复右半部分。
4. 否则（x 更小）在左半边重复出现。

二分查找的递归实现

class Main
{
    // Function to determine if a `target` exists in the sorted array `nums`
    // or not using a binary search algorithm
    public static int binarySearch(int[] nums, int target)
    {
        // search space is nums[left…right]
        int left = 0, right = nums.length - 1;
 
        // loop till the search space is exhausted
        while (left <= right)
        {
            // find the mid-value in the search space and
            // compares it with the target
 
            int mid = (left   right) / 2;
 
            // overflow can happen. Use:
            // int mid = left   (right - left) / 2;
            // int mid = right - (right - left) / 2;
 
            // target is found
            if (target == nums[mid]) {
                return mid;
            }
 
            // discard all elements in the right search space,
            // including the middle element
            else if (target < nums[mid]) {
                right = mid - 1;
            }
 
            // discard all elements in the left search space,
            // including the middle element
            else {
                left = mid   1;
            }
        }
 
        // `target` doesn't exist in the array
        return -1;
    }
 
    public static void main(String[] args)
    {
        int[] nums = { 2, 5, 6, 8, 9, 10 };
        int target = 5;
 
        int index = binarySearch(nums, target);
 
        if (index != -1) {
            System.out.println("Element found at index "   index);
        }
        else {
            System.out.println("Element not found in the array");
        }
    }
}

二分查找的迭代实现

class Main
{
    // Recursive implementation of the binary search algorithm to return
    // the position of `target` in subarray nums[left…right]
    public static int binarySearch(int[] nums, int left, int right, int target)
    {
        // Base condition (search space is exhausted)
        if (left > right) {
            return -1;
        }
 
        // find the mid-value in the search space and
        // compares it with the target
 
        int mid = (left   right) / 2;
 
        // overflow can happen. Use below
        // int mid = left   (right - left) / 2;
 
        // Base condition (a target is found)
        if (target == nums[mid]) {
            return mid;
        }
 
        // discard all elements in the right search space,
        // including the middle element
        else if (target < nums[mid]) {
            return binarySearch(nums, left, mid - 1, target);
        }
 
        // discard all elements in the left search space,
        // including the middle element
        else {
            return binarySearch(nums, mid   1, right, target);
        }
    }
 
    public static void main(String[] args)
    {
        int[] nums = { 2, 5, 6, 8, 9, 10 };
        int target = 5;
 
        int left = 0;
        int right = nums.length - 1;
 
        int index = binarySearch(nums, left, right, target);
 
        if (index != -1) {
            System.out.println("Element found at index "   index);
        }
        else {
            System.out.println("Element not found in the array");
        }
    }
}

性能

本文出至：学新通技术网