二分查找算法(二分查找法多查找多少次)

导语：二分查找 Binary Search

Binary Search: Search a sorted array by repeatedly dividing the search interval in half. Begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.

二进制搜索: 通过不断将要搜素的间隔分裂成一半，来搜索一个已经排好序的数组。首先，一个间隔覆盖整个数组。如果搜索键的值小于间隔中间的项,将搜索区间缩小一半（留值小的一半）。否则将搜索区间缩小一半（留值大的一半）。反复检查间隔,直到找到要找的值或者间隔已经是空的。

The idea of binary search is to use the information that the array is sorted and reduce the time complexity to O(Log n).

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

public class BinarySearch {    // Iterative implementation of Binary Search    public int binarySearch(int[] array, int key){        int l = 0;        int h = array.length - 1;        while(l <= h){            int mid = l + ((h - l) / 2);            if(key  > array[mid]){                l = mid + 1;            }else if(key < array[mid]){                h = mid - 1;            }else{                return mid;            }        }        return -1;    }    //Recursive implementation of Binary Search    public int binarySearchRecursive(int[] array, int key){        return binarySearchRecursive(array, 0, array.length-1, key);    }    private int binarySearchRecursive(int[] array, int l, int h, int key){        if(l <= h){            int mid = l + ((h - l) / 2);            if(key  > array[mid]){                return binarySearchRecursive(array, mid + 1, h, key);            }else if(key < array[mid]){                return binarySearchRecursive(array, l, mid - 1, key);            }else{                return mid;            }        }        return -1;    }    public static void main(String args[]) {        BinarySearch bs = new BinarySearch();        int arr[] = { 2, 3, 4, 10, 40};        int x = 40;        int result = bs.binarySearch(arr, x);        if (result == -1)            System.out.println(&34;);        else            System.out.println(&34; + result);    }}

本文内容由快快网络小茹整理编辑！