第 9 关 | 心有灵犀的二分查找与中序遍历：1.青铜挑战—

1. 基本查找

查找算法中顺序查找算是最简单的了，无论是有序的还是无序的都可以，也不需要排序，只需要一个个对比即可，但其实效率很低，我们来看下代码：

int search(int[] a, int key) {
    for (int i = 0; i < a.length; i++) {
        if (a[i] == key) {
            return i;
        }
    }
    return -1;
}

顺序查找是最简单的一种查找算法，对数据的要求也很随意，不需要排序即可查找。后面会介绍二分法查找，插值查找和斐波那契查找都是基于已经排序过的数据。

2. 二分查找和分治

在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如二分搜索、排序算法(快速排序，归并排序)等等……

任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于n个元素的排序问题，当n=1时，不需任何计算。n=2时，只要作一次比较即可排好序。n=3时只要作3次比较即可，…。而当n较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相当困难的。

二分查找就是将中间结果与目标进行比较，一次去掉一半，因此二分查找可以说是最简单、最典型的分治了。

二分查找，不管是循环还是递归方式，我觉得应该达到写到闭着眼睛，一分钟就能写出来的地步。

这里再补充一个问题，分治和递归是一回事吗？很显然不是。这是两种完全不同的思想，二分查找是分支思想，我们可以使用递归或者循环的方式来做。而很多递归问题也不一定是分治的，因此两个完全不是一回事。

2.1. 循环的方式

常见的使用循环的方式来实现二分查找如下，请问你给多少分？

public  int binarySearch(int[] array, int low, int high, int target) {
    while (low <= high) {
        int mid = (low + high)/2;
        if (array[mid] == target) {
            return mid ; 
        } else if (array[mid] > target) {
            // 由于array[mid]不是目标值，因此再次递归搜索时，可以将其排除
            high = mid -1;
        } else {
            // 由于array[mid]不是目标值，因此再次递归搜索时，可以将其排除
            low = mid + 1;
        }
    }
    return -1;
}

int binarySearch(int array[], int low, int high, int target) {
    while (low <= high) {
        int mid = (low + high) / 2;
        if (array[mid] == target) {
            return mid;
        } else if (array[mid] > target) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return -1;
}

def binarySearch(array, low, high, target):
    while low <= high:
        mid = (low + high) // 2
    if array[mid] == target:
        return mid
    elif array[mid] > target:
        high = mid - 1
    else:
        low = mid + 1
    return -1

在具体操作的时候可能有多种方式的，包括循环体中的 high = mid -1;和low = mid + 1也有多种方式的，这需要与if后面的条件配合，我们不要给自己添麻烦，在理解的基础上熟记这种方式就行了。

如果代码写成这样子，只能得70分，因为有个很重要的细节没有处理。在计算机中，除的效率非常低，一般可以使用移位来代替，也就是

将：
int mid = (low + high) /2;
换成
int mid = (low + high)>>1;

如果这样的话，能得到80分，面试官可能会继续问，还会有什么问题。问题就是假如low和high很大的话，low + high可能会溢出。因此我们可以这么写：

int mid = low+(high - low)>>1;

只要 low和high没有溢出，上面的mid一定不会溢出。

你觉得可以得到90分，很可惜是0分，因为当你测试的时候，可能会出现死循环，例如原始序列是1到8，搜索3的时候就死循环了，为什么呢？

这是因为移位的运算符>>优先级比加减要低，所以上面的代码等价结构是这样的：

（low+(high - low))>>1

很明显这不是我们预期的。解决方法也很简单，加括号就行了。所以最终的代码就是：

python语言里没有该问题，所以代码与上面的一样

public static innt binarySearch(int[] array,intt low,int high.int target){
	while(low <= high){
    	int mid = low + ((high - low) >> 1);
        if(array[mid] == target){
            return mid;
        }else if(array[mid] > target){
            // 由于array[mid]不是目标值，因此再次递归搜索时，可以将其排除
            high = mid - 1;
        }else if(array[mid] < target){
            // 由于array[mid]不是目标值，因此再次递归搜索时，可以将其排除
            low = mid + 1；
        }
	}
	return -1;
}

int binarySearch(int array[], int low, int high, int target) {
    while (low <= high) {
        int mid = low + ((high - low) >> 1);
        if (array[mid] == target) {
            return mid;
        } else if (array[mid] > target) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return -1;
}

这样的话，面试官就提不出什么问题了，而且上面这个优先级问题很多人只是理解了，并没有上机测试，因此很多面试官也不会注意到这里会有死循环的情况。

当然这里还没有考虑元素重复的问题，后面再说。

2.2. 递归的方式

递归就不必多说了，直接看代码:

public  int binarySearch1(int[] array, int low, int high, int target) {
    //递归终止条件
    if(low <= high){
        int mid = low + ((high - low) >> 1);
        if(array[mid] == target){
            return mid  ;  // 返回目标值的位置，从1开始
        }else if(array[mid] > target){
            // 由于array[mid]不是目标值，因此再次递归搜索时，可以将其排除
            return binarySearch(array, low, mid-1, target);
        }else{
            // 由于array[mid]不是目标值，因此再次递归搜索时，可以将其排除
            return binarySearch(array, mid+1, high, target);
        }
    }
    return -1;   //表示没有搜索到
}

int binarySearch(int array[], int low, int high, int target){
    if(low <= high){
        int mid = low + ((high - low) >> 1);
        if(array[mid] == target){
            return mid;
        }else if(target > array[mid]){
            binarySearch()
        }
    }
    return -1;
}

def binarySearch1(array, low, high, target):
    if low <= high:
        mid = low + ((high - low) >> 1)
    if array[mid] == target:
        return mid
    elif array[mid] > target:
        return binarySearch1(array, low, mid - 1, target)
    else:
        return binarySearch1(array, mid + 1, high, target)
return -1

这里的mid的计算和可能出现的问题与上面是一样的。这个也是面试时体现基本功的亮点。如果能写到这种程度，就是满分了，面试官基本不会再说什么了。

3. 元素中有重复的二分查找

假如在上面的基础上，元素存在重复，如果重复则找左侧第一个，请问该怎么做呢？这个我曾在面快手时遇到过。

这里的关键是找到目标结果之后不是返回而是继续向左侧移动。第一种，也是最简单的方式，找到相等位置向左使用线性查找，直到找到相应的位置。

public static int search(int [] nums,int target){
    if(num == null || nums.length == 0){
        return -1;
    }
    int left = 0;
    int right = nums.length - 1;
    while(left <= right){
        int mid = (right - left) / 2 + left;
        if(nums[mid] < target){
            left = mid  + 1;
        }else if(nums[mid] > target){
            right =mid - 1;
        }else{
            //找到之后，往左边找
            while (mid != 0 && nums[mid] == target)
            mid--;
            if (mid == 0 && nums[mid] == target) {
                return mid;
            }    
            return mid + 1;
        }
    }
}

def search(nums, target):
    if nums is None or len(nums) == 0:
        return -1
    left = 0
    right = len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] < target:
            left = mid + 1
        elif nums[mid] > target:
            right = mid - 1
        else:
            # 找到之后，往左边找
            while mid != 0 and nums[mid] == target:
                mid -= 1
            if mid == 0 and nums[mid] == target:
                return mid
            return mid + 1
    return -1

int search(int *nums, int target, int numsSize)
{
    if (nums == NULL || numsSize == 0)
    {
        return -1;
    }
    int left = 0;
    int right = numsSize - 1;
    while (left <= right)
    {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target)
        {
            left = mid + 1;
        }
        else if (nums[mid] > target)
        {
            right = mid - 1;
        }
        else
        {
            // 找到之后，往左边找
            while (mid != 0 && nums[mid] == target)
            {
                mid--;
            }
            if (mid == 0 && nums[mid] == target)
            {
                return mid;
            }
            return mid + 1;
        }
    }
    return -1;
}

注意这里在找到之后的while循环结束后，为什么要返回mid+1，而不是mid呢？这是因为此时nums[mid]已经不等于target了，例如假如序列为{1, 2, 2, 2, 2, 3, 3}，当target=3,当内层的while退出时，nums[mid]=2，因此我们必须返回mid+1。

第 9 关 | 心有灵犀的二分查找与中序遍历：1.青铜挑战——逢试必考的二分查找-灵析社区

1. 基本查找

2. 二分查找和分治

2.1. 循环的方式

2.2. 递归的方式

3. 元素中有重复的二分查找