折半查找

• 折半查找的注意点
  • 折半查找只能查找有序数组的值
• 折半查找的逻辑
  1.把数组第一个元素的索引作为最小值,最后一个元素的索引作为最大值
  2.把(max + min) / 2结果作为数组中间值的索引
  3.把上面索引对应的数组元素和需要查找的值进行比较
  4.如果元素小于比较元素,说明需要查找的元素在数组后半段,则让min = mid + 1并重复以上操作
  5.如果元素大于比较元素,说明需要查找的元素在数组前半段,则让max = mid -1并重复以上操作
  6.如果元素等于比较元素,说明此时的mid是查找的元素

#include <stdio.h>

int main()
{
    //需求:查找元素7所在的位置
    int key = 7;
    int num[5] = {1,3,5,7,9};
    int min = 0;
    int max = sizeof(num) / sizeof(num[0]) - 1;
    int mid = min + (max - min) / 2;
    while(max >= min){
        if(num[mid] > key){
            max = mid - 1;
        }else if(num[mid] < key){
            min = mid + 1;
        }else{
            printf("在第%i个索引位置",mid);
            break;
        }
        mid = (min + max)/2;
    }
    return 0;
}

• 案例
  需求:在有序数组{1,3,5,7,9}中的某一位置插入数字8,使插入后的数组仍然是有序数组,请写出插入的索引.

代码如下:

#include <stdio.h>

int main()
{
    int key = 8;
    int num[5] = {1,3,5,7,9};
    int min = 0;
    int max = sizeof(num) / sizeof(num[0]) - 1;
    int mid = (min + max) / 2;
    while(max >= min){
        printf("%i %i\n",min,max);
        if(num[mid] > key){
            max = mid - 1;
        }else if(num[mid] < key){
            min = mid + 1;
        }else{
            break;
        }
        mid = (min + max)/2;
    }
    printf("在第%i个位置插入",min);
    return 0;
}