c语言_Day12_07_11

上山打老虎

c语言_Day12_07_11

1、二分查找算法

　　也称折半查找，最坏情况查找log2n次
　　算法如下：

• 找到中间元素索引[左右下标平均值]
  
• 通过中间下标找到中间元素
  
• 判断：若中间元素小于目标值则修改左下标(left = mid + 1)；若中间元素大于目标值则修改右下标(right = mid - 1)；若相等则直接返回
  
• 循环：当左下标不大于右下标时继续查找，反之则未找到元素，应跳出循环
  

int main()
{
  // 查找数组
  int arr[] = { 1,2,3,4,5,6,8,9 };
  // 目标元素
  int k = 3;
  // 数组长度
  int length = sizeof(arr) / sizeof(arr[0]);
  // 定义左右下标
  int left = 0;
  int right = length - 1;
  // 定义中间下标
  int mid;
  // 当左下标仍不大于右下标时，查找仍在继续
  while (left <= right)
  {
    // 计算中间下标
    mid = (left + right) / 2;
    // 若中间下标元素小于目标值，则修改左下标
    if (arr[mid] < k)
    {
      left = mid + 1;
    }
    // 若中间下标元素大于目标值，则修改右下标
    else if (arr[mid] > k)
    {
      right = mid - 1;
    }
    // 若中间下标元素等于目标值，则直接返回
    else
    {
      printf("已找到k，数组下标为%d\n", mid);
      break;
    }
  }
  // 当左下标仍大于右下标时，未找到元素
  if (left > right)
  {
    printf("未找到k\n");
  }
  return 0;
}

2、素数算法优化

　　基本算法：试除法

if (num > 1)
{
  for (int i = 2; i < num; i++)
  {
    if (num % i == 0)
    {
      return 0;
    }
  }
  return 1;
}
else
{
  return 0;
}

　　优化：上述算法需要从2遍历至num-1，实际上对于一个整数i，若i = a * b，则a和b中至少有1个数字小于等于i开平方

int isPrime(int num)
{
  
  if (num > 1)
  {
    // 1. 试除法
    //for (int i = 2; i < num; i++)
    //{
    //  if (num % i == 0)
    //  {
    //    return 0;
    //  }
    //}
    //2. 优化
    for (int i = 2; i <= sqrt(num); i++)
    {
      if (num % i == 0)
      {
        return 0;
      }
    }
    return 1;
  }
  else
  {
    return 0;
  }
}
int main()
{
  int count = 0;
  for (int i = 201; i <= 300; i+=2)  // 偶数不可能为素数
  {
    if (isPrime(i))
    {
      printf("%d\n", i);
      count++;
    }
  }
  printf("count = %d\n", count);
  return 0;
}