剑指Offer——二分查找算法

剑指Offer——二分查找算法

前言

     本片博文主要讲解查找算法的相关知识。重点介绍二分查找。

     二分查找算法是在有序数组中用到的较为频繁的一种查找算法,在未接触二分查找算法时,最通用的一种做法是,对数组进行遍历,跟每个元素进行比较,其时间为O(n).但二分查找算法则更优,因为其查找时间为O(lgn)。

     在面试的时候二分查找是用的比较多一种查找算法,如何在面试官面前快速准确得的写出代码决定你是否能够被录取。以前一直以为二分查找很简单,所以就没怎么重视,但是真要在面试官面前对着黑板手写出来,还是漏洞百出。

     1.二分查找的时间复杂度是O(log(n)),最坏情况下的时间复杂度是O(n)。

     2.二分查找的一个条件是待查询的数组是有序的,我们假设这里的数组是升序的。

     3.二分查找的主要思路就是设定两个指针start和end分别指向数组元素的尾两端,然后比较数组中间结点arry[mid]和待查找元素。如果待查找元素小于中间元素,那么表明带查找元素在数组的前半段,那么将end=mid-1,如果待查找元素大于中间元素,那么表明该元素在数组的后半段,将start=mid+1;如果中间元素等于待查找元素,那么返回mid的值。

     譬如数组{1, 2, 3, 4, 5, 6, 7, 8, 9},查找元素6,用二分查找的算法执行的话,其顺序为:

     1.第一步查找中间元素,即5,由于5<6,则6必然在5之后的数组元素中,那么就在{6, 7, 8, 9}中查找;

     2.寻找{6, 7, 8, 9}的中位数,为8,8>6,则6应该在8左边的数组元素中,那么就在{6,7,8}中查找;

     3.寻找{6, 7, 8}的中位数,为7,7>6,则6应该在7左边的数组元素中,那么只剩下6,即找到了。

     二分查找算法就是不断将数组进行对半分割,每次拿中间元素和goal进行比较。

源码

 

package cn.edu.ujn.demo;
 
public class BinarySearch {
 
/**
 * @param args
 */
public static void main(String[] args) {
int [] array = {1,2,3,4,4,7,12};
int len = array.length;
//System.out.println(binarySearchRecursion(array, 7, array[0], array[len-1]));
System.out.println(binarySearchRecursionNon(array, 7, array[0], array[len-1]));
}
/**
 * 二分查找(递归)
 * @param arry 递增数组
 * @param value 待查找数值
 * @param start 起始查找位置
 * @param end 末查找位置
 * @return
 */
private static int binarySearchRecursion(int arry[],int value,int start,int end)
{
    if(start > end)
        return -1;
 
    int mid=start + (end-start)/2;
    if(arry[mid] == value)
        return mid;
 
    else if(value < arry[mid])
    {
        end = mid - 1;
        return binarySearchRecursion(arry,value,start,end);
    }
    else
    {
        start = mid + 1;
        return binarySearchRecursion(arry,value,start,end);
    }
}
/**
 * 二分查找(非递归)
 * @param arry 递增数组
 * @param value 待查找数值
 * @param start 起始查找位置
 * @param end 末查找位置
 * @return
 */
private static int binarySearchRecursionNon(int arry[],int value,int start,int end)
{
while(start <= end){
    int mid=start + (end-start)/2;
    
    if(arry[mid] == value)
        return mid;
    
    else if(value < arry[mid])
    {
        end = mid - 1;
    }
    
    else
        start = mid + 1;
}
return -1;
}
}

 

在轮转后的有序数组上应用二分查找法

     之前我们说过二分法是要应用在有序的数组上,如果是无序的,那么比较和二分就没有意义了。

     不过还有一种特殊的数组上也同样可以应用,那就是“轮转后的有序数组(Rotated Sorted Array)”。它是有序数组,取其中某一个数为轴,将其之前的所有数都轮转到数组的末尾所得。比如{7, 11, 13, 17, 2, 3, 5}就是一个轮转后的有序数组。非严格意义上讲,有序数组也属于轮转后的有序数组——我们取首元素作为轴进行轮转。

     下边就是二分查找法在轮转后的有序数组上的实现(假设数组中不存在相同的元素)

 

/**
 * 在轮转后的有序数组上应用二分查找法
 * @param array
 * @param low
 * @param high
 * @param target
 * @return
 */
int searchInRotatedSortedArray(int array[], int low, int high, int target)
{
    while(low <= high)
    {
        int mid = (low + high) / 2;
        if (target < array[mid])
            if (array[mid] < array[high])	// the higher part is sorted
                high = mid - 1; // the target would only be in lower part
            else 	// the lower part is sorted
                if(target < array[low])	// the target is less than all elements in low part
                    low = mid + 1;
                else
                    high = mid - 1;
 
        else if(array[mid] < target)
            if (array[low] < array[mid])	// the lower part is sorted
                low = mid + 1;	// the target would only be in higher part
            else 	// the higher part is sorted
               if (array[high] < target)   // the target is larger than all elements in higher part
                    high = mid - 1;
                else
                    low = mid + 1;
        else 	// if(array[mid] == target)
            return mid;
    }
    return -1;
}

 

     对比普通的二分查找法,为了确定目标数会落在二分后的哪个部分,我们需要更多的判定条件。但是我们还是实现了O(log n)的目标。

二分查找法的缺陷

     二分查找法的O(log n)让它成为十分高效的算法。不过它的缺陷却也是那么明显的。就在它的限定之上:

     必须有序,我们很难保证我们的数组都是有序的。当然可以在构建数组的时候进行排序,可是又落到了第二个瓶颈上:它必须是数组。

     数组读取效率是O(1),可是它的插入和删除某个元素的效率却是O(n)。因而导致构建有序数组变成低效的事情。

     解决这些缺陷问题更好的方法应该是使用二叉查找树了,最好自然是自平衡二叉查找树了,自能高效的(O(n log n))构建有序元素集合,又能如同二分查找法一样快速(O(log n))的搜寻目标数。

     我们知道在效率方面,传值调用要比传址调用来的低,因为传值调用要进行一次变量的拷贝,而传址调用则是直接对这个变量进行操作。因此在编程中我们应该尽量将参数改为传址调用。

美文美图

《剑指Offer——二分查找算法》

《剑指Offer——二分查找算法》

    原文作者:No Silver Bullet
    原文地址: https://blog.csdn.net/sunhuaqiang1/article/details/52102179
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞