二分法-binarySearch

我不是女神ヾ 2023-07-09 13:27 19阅读 0赞

二分法查找，也称为折半法，是一种在有序数组中查找特定元素的搜索算法。  
**二分法查找的思路如下：**

（1）首先，从数组的中间元素开始搜索，如果该元素正好是目标元素，
    则搜索过程结束，否则执行下一步。
    
    （2）如果目标元素大于/小于中间元素，则在数组大于/小于中间元素的
    那一半区域查找，然后重复步骤（1）的操作。
    
    （3）如果某一步数组为空，则表示找不到目标元素。

**二分法查找的时间复杂度O(logn)。**

**非递归算法：**

结果测试：  
![在这里插入图片描述][20200229005239100.png]

**递归算法：**

结果测试：  
![在这里插入图片描述][2020022900522727.png]

原文链接：https://blog.csdn.net/u012194956/article/details/79103843

## binarySearch官方包 ##

binarySearch方法为二分法查找，所以数组必须是有序的或者是用sort()方法排序之后的。  
**binarySearch(Object\[\], Object key)**  
方法的object\[\]参数是要查找的数组，key参数为要查找的key值。

**方法的返回值有几种：**

1.找到的情况下：如果key在数组中，则返回搜索值的索引。

2.找不到的情况下：

[1] 搜索值不是数组元素，且在数组范围内，从1开始计数，得
     “ - 插入点索引值”；
     [2] 搜索值是数组元素，从0开始计数，得搜索值的索引值；
     [3] 搜索值不是数组元素，且大于数组内元素，索引值为
      – (length + 1);
     [4] 搜索值不是数组元素，且小于数组内元素，索引值为 – 1。

int a[] = new int[] {
        1, 3, 4, 6, 8, 9};  
            int x1 = Arrays.binarySearch(a, 5);  
            int x2 = Arrays.binarySearch(a, 4);  
            int x3 = Arrays.binarySearch(a, 0);  
            int x4 = Arrays.binarySearch(a, 10);
    int a[] = new int[] {
        1, 3, 4, 6, 8, 9};  
            int x1 = Arrays.binarySearch(a, 5);  
            int x2 = Arrays.binarySearch(a, 4);  
            int x3 = Arrays.binarySearch(a, 0);  
            int x4 = Arrays.binarySearch(a, 10);

**结果为：x1=-4 x2=2 x3=-1 x4=-7**

binarySearch(Object\[\], int fromIndex, int toIndex, Object key)

方法的object\[\]参数为要查找的数组，fromindex参数为开始索引（包括），toindex为结束索引（不包括），两个参数之间为查找的范围。key为要查找的key。

**方法的返回值有几种：**

1.找到的情况下：如果key在数组中，则返回搜索值的索引。

**2.找不到的情况下：**

[1] 该搜索键在范围内，但不是数组元素，由1开始计数，得
     “ - 插入点索引值”；
     [2] 该搜索键在范围内，且是数组元素，由0开始计数，得搜索值的索引值；
     [3] 该搜索键不在范围内，且小于范围（数组）内元素，返回
     –(fromIndex + 1)；
     [4] 该搜索键不在范围内，且大于范围（数组）内元素，返回
      –(toIndex + 1)。

int a[] = new int[] {
        1, 3, 4, 6, 8, 9};  
            int x1 = Arrays.binarySearch(a, 1, 4, 5);  
            int x2 = Arrays.binarySearch(a, 1, 4, 4);  
            int x3 = Arrays.binarySearch(a, 1, 4, 2);  
            int x4 = Arrays.binarySearch(a, 1, 4, 10);
      int a[] = new int[] {
        1, 3, 4, 6, 8, 9};  
            int x1 = Arrays.binarySearch(a, 1, 4, 5);  
            int x2 = Arrays.binarySearch(a, 1, 4, 4);  
            int x3 = Arrays.binarySearch(a, 1, 4, 2);  
            int x4 = Arrays.binarySearch(a, 1, 4, 10);

**结果为 x1=-4 x2=2 x3=-2 x4=-5**

原文链接：https://blog.csdn.net/wanderlustLee/article/details/79208630

[20200229005239100.png]: https://img-blog.csdnimg.cn/20200229005239100.png
[2020022900522727.png]: https://img-blog.csdnimg.cn/2020022900522727.png