当前位置: 首页> 文旅> 文化 > 中国社会科学院_个人简介ppt免费模板_百度竞价排名平台_收录优美的图片

中国社会科学院_个人简介ppt免费模板_百度竞价排名平台_收录优美的图片

时间:2025/7/10 12:04:16来源:https://blog.csdn.net/Edward1027/article/details/142257235 浏览次数:0次
中国社会科学院_个人简介ppt免费模板_百度竞价排名平台_收录优美的图片

文章目录

    • 1.算法思想
    • 2.代码实现
      • (1)循环实现
      • (2)递归实现
    • 3.题目练习

1.算法思想

二分查找(折半查找):有序数组(升序或降序,可以不连续),每次缩小一半的区间。
时间复杂度:O(log n)
空间复杂度:循环实现是 O(1),递归实现是 O(log n)



2.代码实现

C语言求数组长度:

int n = sizeof(A)/sizeof(A[0]);

(1)循环实现

1.C语言实现

//binarySearch.c : 二分查找(折半查找):要求数组必须是有序的(升序或降序,可以不连续)
#include <stdio.h>int binarySearch(int A[], int n, int key)
{int left = 0, right = n-1;while(left <= right){int mid = left + (right-left)/2;if(key < A[mid]){        //目标key在左半区间right = mid-1;}else if(key > A[mid]){  //目标key在右半区间left = mid+1;}else{                   //key == midreturn mid;}}return -1;
}int main()
{int A[] = {01,20,27,59,71,3702,10247};  int n = sizeof(A)/sizeof(A[0]);int pos = binarySearch(A,n,10247);printf("pos = %d\n", pos);return 0;
}

2.C++实现

#include <iostream>
#include <vector>
using std::cout;
using std::vector;int binarySearch(const vector<int>& arr, int target)
{int left = 0, right = arr.size()-1;while(left <= right){//mid的声明要放在循环里面int mid = left + (right-left)/2;  //避免整数溢出if(target < arr[mid]){       //目标在左半区间right = mid -1;}else if(target > arr[mid]){ //目标在右半区间left = mid + 1;}else{return mid;}}return -1;
}int main()
{//二分查找要求是有序数组vector<int> arr = {1,3,5,7,9,11,13,15,17,19,21,23};int target = 21;int pos = binarySearch(arr, target);if(pos == -1){cout << "未找到目标值" << target << "\n";}else{cout << "目标值" << target << "的下标为" << pos << "\n";}return 0;
}

(2)递归实现

//二分查找(折半查找):要求数组必须是有序的(升序或降序,可以不连续)#include <stdio.h>//1.循环实现
int binarySearchIterative(int A[], int n, int key)
{int left = 0, right = n-1;while(left <= right){int mid = left + (right-left)/2;if(key < A[mid]){        //目标key在左半区间right = mid-1;}else if(key > A[mid]){  //目标key在右半区间left = mid+1;}else{                   //key == midreturn mid;}}return -1;
}//2.递归实现
int binarySearchRecursive(int A[], int left, int right, int key)
{//递归出口if(left > right)    return -1;//递归公式int mid = left + (right-left)/2;if(key < A[mid]){        //目标在左半区间return binarySearchRecursive(A, left, mid-1, key);}else if(key > A[mid]){  //目标值在右半区间return binarySearchRecursive(A, mid+1, right, key);}else{                   //目标值 == A[mid]return mid;}
}int main()
{int A[] = {1,20,27,59,71,88,100,3702,10247};  int n = sizeof(A)/sizeof(A[0]);while(1){int key;printf("请输入要查找的数字: ");scanf("%d",&key);int posI = binarySearchIterative(A,n,key);int posR = binarySearchRecursive(A,0,n-1,key);printf("posI = %d\n", posI);printf("posR = %d\n", posR);}return 0;
}



3.题目练习

1.力扣704:二分查找
https://leetcode.cn/problems/binary-search/

参考答案:C语言实现

//二分查找的循环实现
int search(int* nums, int numsSize, int target) {int left = 0, right = numsSize-1;while(left <= right){int mid = left + (right-left)/2;if(target < nums[mid]){        //目标在左半区间right = mid-1;}else if(target > nums[mid]){  //目标在右半区间left = mid+1;}else{                         //target == nums[mid]return mid;}}return -1;
}
关键字:中国社会科学院_个人简介ppt免费模板_百度竞价排名平台_收录优美的图片

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: