论坛 › 物联网 › 算法——二分查找

熊熊出没 发表于 2024-8-10 23:03:01

算法——二分查找

一、算法原理

二分查找是一种在有序数组中查找特定元素的算法。它的基本思想是通过比较数组中心元素和目的值的大小关系，来确定目的值在数组的哪一部门，然后不停缩小查找范围直到找到目的值大概确定目的值不存在为止。
注：查找数组必须是有序数组
二、算法实现流程

https://i-blog.csdnimg.cn/direct/380e29b4c99f425788f86f74e0c41bce.png
https://i-blog.csdnimg.cn/direct/06365f4e315244a889305958e411075e.png
 三、代码示例

int binary_search(int *arr,int size,int target)
{
    int low = 0;                  /*定义最低下标为记录首位*/
    int high = size - 1;            /*定义最高下标为记录末位*/
    while(low <= high)
    {
      int mid = (low + high) / 2;   /*折半*/
      if(arr == target)      /*若相等，这说明mid为查找到的位置*/
      {
            return mid;
      }
      else if(arr > target)/*若查找值比中值小，最高位下标调整到中位下标小一位*/
      {
            high = mid - 1;
      }
      else{                     /*若查找值比中值大，最低位下标调整到中位下标大一位*/
            low = mid + 1;
      }
    }
    return -1;            /*如果上述循环结束后，没有找到指定值，返回-1*/
}

int main()
{
    int arr[] = {1,10,20,25,36,41,50,56,60};
    int size = sizeof(arr) / sizeof(int);
    int ret = binary_search(arr,size,56);
    printf("ret === %d\n",ret);
    return 0;
} 运行结果：找到56的下标为7
https://i-blog.csdnimg.cn/direct/777edc93f5d54171b9bb4fee48ffbfee.png


免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

查看完整版本: 算法——二分查找