折半查找 二分查找

1. 适用范围:

1. 顺序排列的线性表
   1. 且数据分布不均匀
2. 寻找目标关键字相邻的关键字
   1. low指向较小的相邻记录
   2. high指向较大的相邻记录
3. 将有序数据/数组划分为两部分
4. 获取边界信息

1. 算法分析:

平均查找长度ASL: $lo{g}_2(n+1)-1$

基本概念

• base::折半查找中的判定二叉树

2. 算法思想:

child::二分思想

3. 在c语言的实现

1. 代码:

#include <stdio.h>
 
int binarySearch(int arr[], int n, int target) {
    int low = 0;
    int high = n - 1;
    
    while (low <= high) {
        int mid = low + (high - low) / 2;
        
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    
    return -1; // target not found
}
 
int main() {
    int arr[] = {1, 3, 5, 7, 9, 11, 13};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 7;
    
    int result = binarySearch(arr, n, target);
    
    if (result != -1) {
        printf("Target found at index: %d\n", result);
    } else {
        printf("Target not found\n");
    }
    
    return 0;
}

输出:

Target found at index: 3

参考链接:

• Binary Search on Wikipedia

4. 在JavaScript/ts中的实现:

1. 代码:

function binarysearch(rcds:record[],key:keytype){
    let low=-1,high=rcds.length,mid:number;
    for(;low+1!=high;){
        mid=(low+high)>>1;
        if(rcds[mid].key==key){
            return mid;
        }
        else if(rcds[mid].key<key){
            low=mid;
        }
        else{
            high=mid;
        }
    }
    /*运行至此,搜索不成功,则low与high分别指向最靠近目标的两个数*/
    /*当然查找目标处于边界时,low或high会越界*/
    return null;
}