二分查找的递归与非递归实现

二分法查找

如何用最省内存的方式实现快速查找功能

算法思想

二分法查找针对的是一个有序的数据集合,每次通过与区间的中间元素对比,将待查找的区间缩小为之前的一半,直到找到要查找的元素,或者区间被缩小为0

二分查找非常高效,假设数据大小是n,每次查找后数据都会缩小为原来的一半,也就是会除以2,最坏情况下,直到查找区间被缩小为空,才停止

当n/2k = 1时,k是总共缩小的次数,而每一次缩小操作只涉及两个数据的大小比较,经过K次区间缩小的操作,时间复杂度就是O(k),n/2k = 1得到k=log2 n,故时间复杂度就是O(logn)

图解

a4dcc407efe745909fc97b91b76df63d.gif

递归方式

    /**
     * 二分查找(递归实现)
     * @param array
     * @return
     */
    private static int binarySearch(int[] array, int left, int right, int val) {
	if(left>right){//结束递归的条件
            return -1;
        }	
        int mid=(left+right)>>1;
        if(array[mid]==val){
            return mid;//说明中间的数就是要找的数
        }else if(array[mid]>val){
            //说明在左边
            right=mid-1;
        }else(array[mid]<val){
            //说明在右边
            left=mid+1;
        }

       
        return binarySearch(array,left,right,val);
        
    }

非递归方式


    /**
     * 二分法查找(非递归方法)
     * @param array
     * @param val
     * @return
     */
    public static int binarySearch2(int[] array,int val){
        int left=0;
        int right=array.length-1;
        while (left<=right){
            int mid=(left+right)>>2;
            if(array[mid]==val){
                return mid;
            }
            if(array[mid]>val){
                right=mid-1;
            }
            if(array[mid]<val){
                left=mid+1;
            }
        }
        return -1;
    }

完整代码

package com.coderman.datastruct.search;

/**
 * 二分查找算法
 * @Author zhangyukang
 * @Date 2020/3/5 16:48
 * @Version 1.0
 **/
public class BinarySearch {

    private static final int NUM=3;

    public static void main(String[] args) {
        int[] array={3,6,8,7,4,1,0,9};
        sort(array);//先排好序
        print(array);
        int index=binarySearch2(array,NUM);
        System.out.println(NUM+"所在的位置是:"+index);
    }

    /**
     * 二分查找(递归实现)
     * @param array
     * @return
     */
    private static int binarySearch(int[] array, int left, int right, int val) {
        if(left>right){//结束递归的条件
            return -1;
        }	
        int mid=(left+right)>>1;
        if(array[mid]==val){
            return mid;//说明中间的数就是要找的数
        }else if(array[mid]>val){
            //说明在左边
            right=mid-1;
        }else(array[mid]<val){
            //说明在右边
            left=mid+1;
        }
      
        return binarySearch(array,left,right,val);
    }

    /**
     * 二分法查找(非递归方法)
     * @param array
     * @param val
     * @return
     */
    public static int binarySearch2(int[] array,int val){
        int left=0;
        int right=array.length-1;
        while (left<=right){
            int mid=(left+right)>>1;
            if(array[mid]==val){
                return mid;
            }
            if(array[mid]>val){
                right=mid-1;
            }
            if(array[mid]<val){
                left=mid+1;
            }
        }
        return -1;
    }

    /**
     * 二分查找需要有序的数组
     * @param array
     */
    private static void sort(int[] array) {
        for(int i=0;i<array.length-1;i++){
            int minPos=i;
            for(int j=i+1;j<array.length;j++){
                if(array[minPos]>array[j]){
                    minPos=j;
                }
            }

            if(minPos!=i){
                int temp=array[i];
                array[i]=array[minPos];
                array[minPos]=temp;
            }
        }

    }

    /**
     * 打印
     * @param array
     */
    private static void print(int[] array){
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]+"\t");
        }
        System.out.println();
    }

}

应用场景

二分查找依赖顺序表结构

二分查找不能依赖如链表的的其他结构,主要原因是二分查找算法需要按照下标随机访问元素,链表随机访问的时间复杂度是O(n),使用链表存储,二分查找的时间复杂度就会变得很高

二分查找针对的有序数组

二分查找对数据要求必须是有序的,如果数据没有序,则需要先排序

数据量太小或数据量太大也不适合二分查找

输出结果

0	1	3	4	6	7	8	9	
3所在的索引位置是:2
# 算法   查找  

评论

公众号:mumuser

企鹅群:932154986

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×