二分查找（折半查找） 之二

前情提要：写的也太垃圾了感觉，不忍看

参考：

$fileName
流程图 
int search( int a[], int length, int target ){
    int left = 0;
    int right = length-1;       // 左闭右开: int right = length; 
    
    while( left <= right ){
        int middle = left + (right - left) / 2;

        if ( target < a[middle] )
            right = middle - 1;  // 左闭右开：right = middle;
        else if ( target > a[middle] )
            left = middle + 1;
        else
            return middle;
    }
    return -1;
}

一、使用条件

  • 线性表中的记录必须按关键码有序
  • 必须采用顺序存储

二、low <= high ？

之前我也有疑问，为什么呢？

$fileName
low、high、mid 重合

如上图，在数组中查找 12，而 12 是不存在的。但当查找到最后一步三者重合时，由于区间变化规律，还是会继续查找，此时 high 和 low 交错，会无限循环——由于没有终止条件 while(low <= high)。

$fileName
low、high 交错，退出循环

所以，while(low <= high)（或者while(low < high)）是为了在找不到target时顺利地退出循环。

三、作业

课上小任务，5分钟。

$fileName
小任务 
/**
 * @version:
 * @author: @Akari
 * @date: 2024-01-11 17:27:44
 **/
#include <stdio.h>      // 二分查找 binarySearch

int binarySearch(int array[], int arrLength, int targetNumber);

int main(void)
{
    
    int array[] = {0, 5, 13, 19, 22, 41, 55, 68, 72, 81, 98};
    int targetNumber, result;
    int arrLength = sizeof(array) / sizeof(array[0]);   // 获得数组长度
    
    printf("输入在以下数组中要查找的数字：\n");
    for ( int i = 0; i < 10; i++ ){
        printf("%d ", array[i]);
    }
    printf("\n");
    scanf("%d", &targetNumber);
    
    result = binarySearch(array, arrLength, targetNumber);
    if ( -1 == result )
        printf("Not Found.");
    else
        printf("Found! Target index: %d\n", result + 1);

    return 0;
}

int binarySearch(int array[], int arrLength, int targetNumber){
    int low = 0;
    int high = arrLength - 1;   // 左闭右开式：high = arrLength
    
    while ( low <= high ){
        int mid = low + (high - low) / 2;   // 防止越界
        
        if ( targetNumber > array[mid] )
            low = mid + 1;
        else if ( targetNumber < array[mid] )
            high = mid - 1;     // 左闭右开时：high = mid
        else
            return mid;
    }
    return -1;
}

四、总结

$fileName
总结

4.1 老师推荐的刷题网站

NOI / 1.11编程基础之二分查找：http://noi.openjudge.cn/ch0111/

也就是小结中的第三点，不仅可以查找数据，还可以解决数学问题、几何问题。

4.2 sizeof(array) / sizeof(array[0])

int arrLength = sizeof(array) / sizeof(array[0]);   // 获得数组长度

sizeof 是一个运算符，用于计算数据类型或对象所占用的字节数。对于数组，sizeof(array) 返回整个数组所占用的字节数，而 sizeof(array[0]) 返回数组中单个元素的字节数。

通过将整个数组所占用的字节数除以单个元素的字节数，就可以得到数组中元素的个数。这是因为整个数组所占用的字节数除以单个元素的字节数就是数组中元素的个数。