数据结构和算法-15-二分查找

柔情只为你懂 2021-12-24 10:31 218阅读 0赞

前面学习了六种排序算法，接着学习搜索，搜索中使用最多一种简单查找方法就是二分查找。二分查找的特点是，先保证数列是有序排序，然后每次查找可以减少一半的范围，直到查到或者找不到目标元素为止。这个也是经常在面试中被要求手写这个查找代码，接着要你设计测试用例去测试你写的代码。

**1.二分查找定义**

二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好。其缺点就是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。首先，假设表中元素是按升序排列，将表中间位置纪录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置纪录将表分成前后两个子表。如果中间位置纪录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的纪录，使查找成功，或者直到子表不存在为止，此时查找不成功。

**2.二分查找图解**

例如有下面一个数列，二分查找算法如下，上半部分是二分查找，下半部分是顺序查找。

![461877-20160721092729169-843824718.gif][]

二分查找的好处，每次查询一遍之后，接下来要查找范围缩小了一般。上图刚好是二分查找的最坏情况和顺序查找的最优情况对比。

**3.二分查找代码实现**

Python代码实现

先来看看递归的方式实现

# coding:utf-8
    
    
    def binary_search(alist, item):
        """二分查找"的递归实现"""
        n = len(alist)
    
        if n > 0:
            mid = n // 2
            if alist[mid] == item:
                return True
            elif item < alist[mid]:
                return binary_search(alist[:mid], item)
            else:
                return binary_search(alist[mid+1:], item)
    
        return False
    
    
    if __name__ == "__main__":
        li = [1, 3, 6, 7, 11, 20, 39]
        print(binary_search(li, 39))
        print(binary_search(li, 44))

运行结果

True
    False

再来看看第二种方式，非递归方法

# coding:utf-8
    
    
    def binary_search(alist, item):
        """二分查找"的非递归实现"""
        n = len(alist)
        first = 0
        last = n-1
    
        while first <= last:
            mid = (first + last) // 2
            if alist[mid] == item:
                return alist.index(item)
            elif alist[mid] < item:
                first = mid + 1
            else:
                last = mid - 1
        return -1
    
    
    if __name__ == "__main__":
        li = [1, 3, 6, 7, 11, 20, 39]
        print(binary_search(li, 39))
        print(binary_search(li, 44))

上面的设计是如果找到了就返回该元素在数列中的下标也就是索引，找不到返回-1.

运行结果

6
    -1

Java代码实现

第一种递归实现

第二种非递归实现

package com.anthony.test;
    
    import java.util.Arrays;
    
    public class BinarySearch {
    
        public static void main(String[] args) {
            int[] arr = {1, 3, 6, 7, 11, 20, 39};
            System.out.println(binarySeach_02(arr, 39));
            System.out.println(binarySeach_02(arr, 44));
        }
    
        public static int binarySeach_02(int[] arr, int item) {
            
            //1.定义最小索引，最大索引，中间索引的标记
            int max = arr.length - 1;
            int min = 0; 
            int mid = (min+max)/2;
            
            //2 当中间值不等于要找的值，就开始循环
            while (arr[mid] != item) {
                if(arr[mid] < item) {
                    // 说明目标元素在右半部分，最小的索引改变
                    min = mid + 1;
                }else if (arr[mid] > item) {
                    // 说明目标元素在左侧半部分，最大的索引改变
                    max = mid - 1;
                }
                // 由于上面min或者max发生了改变，所以mid需要重新获取新的值
                mid = (min + max)/2;
                // 如果最小索引大于最大索引就没有查找的可能性，返回-1
                if(min > max) {
                    return -1;
                }
            }
            return mid;
    
        }
    }

运行结果

6
    -1

**4.针对上面java版本非递归方法的单元测试**

这个题目，我在滴滴面试过程中遇到过，当时每考虑全测试点。

测试点1：100%语句覆盖

因为是白盒测试，这里先来一个百分百语句覆盖的测试用例。我们二分查找的思路就是，先和中间元素比较，这是一个代码分支，然后比较左半部分，这是第二个代码分支测试点，然后是右半部分列表去查找，这是第三个代码分支测试点。所以，我们先来一个只有三个元素的数列，然后分别去查找三次，第一次查找第一个元素代表左半部分代码路径覆盖，第二次查找中间元素，这个时候刚好覆盖arr\[mid\]== item这个代码分支，第三次查找第三个元素，模拟右半部分数列的二分查找。，第四次查找模拟查找不到的情况。三次查找，四个测试用例，我们在一个junit的方法中覆盖。

把Java第二种方法的二分查找写到一个类中，作为静态工具类使用。

package test;
    
    import org.junit.Test;
    
    public class TestBinarySearch {
    	
    	@Test
    	public void test1() {
    		System.out.println("100%代码路径覆盖测试");
    		int[] arr = {1, 2, 3};
    		int item1 = 1;
    		int item2 = 2;
    		int item3 = 3;
    		int item4 = 4;
    		System.out.println(BinarySearch.binarySeach_02(arr, item1));
    		System.out.println(BinarySearch.binarySeach_02(arr, item2));
    		System.out.println(BinarySearch.binarySeach_02(arr, item3));
    		System.out.println(BinarySearch.binarySeach_02(arr, item4));
    	}
    
    }

运行结果

100%代码路径覆盖测试
    0
    1
    2
    -1

测试点2：分支覆盖测试

我们这里代码分支，有两个，一个是元素在左半部分，第二个是元素在右半部分。所以，这里我们测试用例设计没有上面这个用例考虑全面，这里我们只是测试if -else这两个分支，下面用例代表左半部分元素查找和右半部分查找的使用场景。

@Test
    public void test2() {
    	System.out.println("分支覆盖测试");
    	int[] arr = {1, 2, 3, 4, 5, 6, 7, 9};
    	int item1 = 2;
    	int item2 = 7;
    	System.out.println(BinarySearch.binarySeach_02(arr, item1));
    	System.out.println(BinarySearch.binarySeach_02(arr, item2));
    }

测试点3：谓词完全覆盖测试

这个谓词覆盖，我也是第一次听说，这种概念的东西，其实不实用。简单来说代码中谓词就是 ！=， > <这样的代码。所以，下面设计用例其实和上面分支覆盖是一样的用例。

@Test
    public void test3() {
    	System.out.println("谓词覆盖测试");
    	int[] arr = {1, 2, 3, 4, 5, 6, 7, 9};
    	int item1 = 0;
    	int item2 = 6;
    	System.out.println(BinarySearch.binarySeach_02(arr, item1));
    	System.out.println(BinarySearch.binarySeach_02(arr, item2));
    }

上面查找0，覆盖了while 中的！=这个判断，查找6覆盖了分支中大于和小于的判断。

测试点4：缺陷测试（没有完整覆盖路径）

缺陷就是用例只覆盖了代码中一部分代码，例如一个列表，我们只查找一个元素，肯定一次执行不能覆盖全部代码。

@Test
    public void test4() {
    	System.out.println("有缺陷");
    	int[] arr = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18};
    	int item1 = 11;
    	System.out.println(BinarySearch.binarySeach_02(arr, item1));
    }

为了解决这个缺陷问题，我们可以写一个依次查找列表中每一个元素和一个不存在的元素，也能覆盖全部代码路径。

@Test
    public void test5() {
    	System.out.println("没缺陷的覆盖查询");
    	int[] arr = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18};
    	int item1 = 0;
    	System.out.println(BinarySearch.binarySeach_02(arr, item1));
    	for (int i : arr) {
    		System.out.println(BinarySearch.binarySeach_02(arr, i));
    	}
    }

[461877-20160721092729169-843824718.gif]: /images/20211224/134c47dac8e347aaa9f3a09c9137b549.png