首页 > 代码库 > 折半查找

折半查找

2024-11-21 06:43:02   204人阅读

网上看到的，不是C的，改成了C的……

===========================

一. 方法原理

当从一个给定的序列数组arr中, 查找某个特定值value时, 折半搜索法是这样做的:

1. 确定搜索范围的起始点: 起点start = 0, 终点end = 数组长size – 1;

2. 根据起始点来确定一个中间点middle = (终点 + 起点) / 2;

3. 在start < end的前提下, 比较arr[middle]与value的大小:

(1) arr[middle] < value 调整搜索范围为数组的后半部分, 即start = middle + 1, end = size - 1;

(2) arr[middle] > value 调整搜索范围为数组的前半部分, 即start = 0, end = middle - 1; 接着, 重新计算middle, 再比较arr[middle]与value, 直到两者相等或者start >= end.

技术分享
 1 // 折半搜索示例程序 2 #include <stdio.h> 3  4  int search(int arr[], int size, int num); 5  6  int main(void) 7  { 8      int arr[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; 9      int num;10      int value;11 12      printf("Please input one integer number: \n");13      scanf("%d", &num);14      value = http://www.mamicode.com/search(arr, 10, num);15      if(value)16          printf("Array contain %d\n", num);17      else18          printf("Array no contain %d\n", num);19      return 0;20  }21 22  int search(int arr[], int size, int num)23  {24      int start = 0;25      int end = size - 1;26      int middle = (start + end) / 2;27 28      while(arr[middle] != num && start < end)29      {30          if(arr[middle] < num)31              start = middle + 1;32          else if(arr[middle] > num)33              end = middle - 1;34          middle = (start + end) / 2;35      }36      return (arr[middle] == num) ? 1 : 0;37  }
View Code

 

折半查找


联系
我们