C语言—实现二分查找（1）

—，顺序查找和二分查找
二：逻辑
三，代码实现和结果
四，知识点

—，顺序查找和二分查找

顺序查找：从第一个数字一个一个往后找，直到找到为止。

                ag:有一组有序数字：1，2，3，4，5，6，7，8，9，10；从这组数字中找出数字7。  若按顺序查找，第一个找到的数字为1，不等于7；继续找，第二个找到的数字为2，不等于7；以此类推，直到找到7停止，一共找了7次。按照这种方式查找，最坏的查找次数为n次。可见，这种查找方式效率低。

二分查找：二分查找也称折半查找，它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

ag:有一组有序数字：1，2，3，4，5，6，7，8，9，10；从这组数字中找出数字7。   按二分查找的方法，先找出中间的数（5），再与要找的数字k进行比较，若5<k,查找范围变成了6到10；若5>k,查找范围变为1到4，然后再在查找范围里进行二分查找，直到找到为止，一共找了3次。可见，这种方法效率高。

二：逻辑

三：代码实现和结果

#include<stdio.h>

//在一个数组中查找具体的某个数

int main()

{

int arr[]={1,2,3,4,5,6,7,8,9,10};

int k=7;

int sz=sizeof(arr)/sizeof(arr[0]);

int left=0;    //左下标

int right=sz-1;     //右下标

while(left<=right)  //二分查找的次数>=1

{

int mid=(left+right)/2;    //要注意执行下面语句后left,right都改变了

if(arr[mid]<k)     //mid在k的左边

left=mid+1;   //右下标不变，左下标=mid+1

else if(arr[mid]>k)  mid在k的右边

right=mid-1;   //左下标不变，右下标=mid-1

else                          //不能使用3个if语句

{

printf("找到了，下标是%d\n",mid);

break;

}

}

if(left>right)

printf("找不到\n");return 0;}

让k=17，结果：

四：知识点

1、​数组内元素的个数=数组的空间大小除以数组内一个元素的空间大小

2、sizeof()函数：计算变量、数组、类型的大小，单位是字节

     sizeof(arr):计算arr所占空间大小