Java实现折半查找

怼烎@ 2024-03-24 14:59 17阅读 0赞

### 1. 算法思想 ###

折半查找又称为二分查找，仅适用于有序的顺序表。  
把数组看成一个大区间，每次把区间一分为二。判断目标元素是在左区间还是右区间，如果是在左区间上，把查找区间切换到左区间上，再进行划分，循环往复，直至查找失败或者成功为止。  
![在这里插入图片描述][e0e0f76249f34513a737e22fc5cc3c60.png]

### 2. 代码实现 ###

定义二分查找类并实现查找算法。

public class BinarySearch {
        
        public int search(int[] a, int key){
        
            // 指向第一个元素
            int low = 0;
            // 指向第最后一个元素
            int high = a.length - 1;
            int mid;
            //查找成功的情况
            while (low <= high)
            {
        
                // 指向中间元素
                mid = (low + high) >> 1;
               // 如果中间元素为目标元素直接返回中间元素的索引
                if (a[mid] == key)
                    return mid;
                // 如果中间元素比目标元素要大，说明目标元素在左区间上
                else if (a[mid] > key)
                    high = mid - 1;
                // 如果中间元素比目标元素小，说明目标元素在右区间上
                else
                    low = mid + 1;
            }
            // 查找失败返回-1
            return -1;
        }
    }

### 3. 测试 ###

编写测试代码进行效果测试。

public class BinarySearchTest {
        
        public static void main(String[] args) {
        
            int[] a={
        10,25,35,48,56,78,89};
            BinarySearch binarySearch = new BinarySearch();
            int index = binarySearch.search(a, 56);
            System.out.println(index);
        }
    }

![在这里插入图片描述][fb084c2ec14e47e99e44fcb4efbef1f2.png]

### 4. 查找效率分析 ###

根据查找判定树分析查找成功和失败的查找效率。  
![在这里插入图片描述][95c9675678234f059ce69f84be4f1cde.png]

#### 4.1 查找成功的平均查找长度： ####

ASL：(1 + 2 \* 2 + 4 \* 3 + 4 \* 4) / 11 = 3

#### 4.2 查找失败的平均查找长度： ####

ASL：(4 \* 4 + 8 \* 5) / 12 = 11/3

[e0e0f76249f34513a737e22fc5cc3c60.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/7610b21193e540ca8939979f92e53b0a.png
[fb084c2ec14e47e99e44fcb4efbef1f2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/05f38e6851e142df95828369e5381970.png
[95c9675678234f059ce69f84be4f1cde.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/bfa3c137806340d8a07c446cdc860ff9.png