二分查找法 java实现(折半查找)

算法要求:

1.必须采用顺序存储结构。

2.必须按关键字大小有序排列。

算法复杂度:

二分查找的基本思想是将n个元素分成大致相等的两部分，取a[n/2]与x做比较，如果x=a[n/2],则找到x,算法中止；如果x<a[n/2],则只要在数组a的左半部分继续搜索x,如果x>a[n/2],则只要在数组a的右半部搜索x.

时间复杂度无非就是while循环的次数！

总共有n个元素，

渐渐跟下去就是n,n/2,n/4,….n/2^k（接下来操作元素的剩余个数），其中k就是循环的次数

由于你n/2^k取整后>=1

即令n/2^k=1

可得k=log2n,（是以2为底，n的对数）

所以时间复杂度可以表示O(h)=O(log2n)

算法实现(java):

public class ErFenTest {


    public static int recursionBinarySearch(int[] arr,int key,int low,int high){

        if(key &lt; arr[low] || key &gt; arr[high] || low &gt; high){
            return -1;
        }

        int middle = (low + high) / 2;          //初始中间位置
        if(arr[middle] &gt; key){
            //比关键字大则关键字在左区域
            return recursionBinarySearch(arr, key, low, middle - 1);
        }else if(arr[middle] &lt; key){
            //比关键字小则关键字在右区域
            return recursionBinarySearch(arr, key, middle + 1, high);
        }else {
            return middle;
        }

    }



    /**
     * 不使用递归的<a href="https://www.wangt.cc/tag/%e4%ba%8c%e5%88%86%e6%9f%a5%e6%89%be/" title="查看更多关于二分查找的文章" target="_blank">二分查找</a>
     *title:commonBinarySearch
     *@param arr
     *@param key
     *@return 关键字位置
     */
    public static int commonBinarySearch(int[] arr,int key){
        int low = 0;
        int high = arr.length - 1;
        int middle = 0;         //定义middle

        if(key &lt; arr[low] || key &gt; arr[high] || low &gt; high){
            return -1;
        }

        while(low &lt;= high){ middle = (low + high) / 2; if(arr[middle] &gt; key){
                //比关键字大则关键字在左区域
                high = middle - 1;
            }else if(arr[middle] &lt; key){
                //比关键字小则关键字在右区域
                low = middle + 1;
            }else{
                return middle;
            }
        }

        return -1;      //最后仍然没有找到，则返回-1
    }


    /**
     * 使用递归的<a href="https://www.wangt.cc/tag/%e4%ba%8c%e5%88%86%e6%9f%a5%e6%89%be/" title="查看更多关于二分查找的文章" target="_blank">二分查找</a>
     *title:recursionBinarySearch
     *@param arr 有序数组
     *@param key 待<a href="https://www.wangt.cc/tag/%e6%9f%a5%e6%89%be/" title="查看更多关于查找的文章" target="_blank">查找</a>关键字
     *@return 找到的位置
     */
    public static void main(String[] args){
        int[] tem={1,2,3,4,5,6,7,8};
        //test 递归
        System.out.println(&quot;<a href="https://www.wangt.cc/tag/%e6%9f%a5%e6%89%be/" title="查看更多关于查找的文章" target="_blank">查找</a>结果所在的位置: &quot;+ErFenTest.recursionBinarySearch(tem,3,0,tem.length-1));


        //test 非递归
        System.out.println(&quot;<a href="https://www.wangt.cc/tag/%e6%9f%a5%e6%89%be/" title="查看更多关于查找的文章" target="_blank">查找</a>结果所在的位置: &quot;+ErFenTest.commonBinarySearch(tem,3));

    }
}