|
1、二分查找的介绍
二分查找又称折半查找，是一种很经典的查找算法，其目的就在于在一组数据中寻找元素key，其核心就在于用一组数据的中位数，去与想要查找的元素key进行比较，每次比较都能筛去一半不符合要求的数据，通过循环最终去找到元素key，返回下标，或者发现这组数据中不存在元素key，此时返回 -1
因此二分查找的时间复杂度为O（logn）
2、二分查找的使用要求
这组数据需要是有序的，因为我们每次排除一半不符合要求的数据的前提就在这里
3、 画图理解
4、代码实现
int Binary_search(int arr[], int sz, int key)
{
int left = 0;
int right = sz - 1;
int mid = 0;
//我们只需要考虑left和right之间的数
//直到left == right都还没找到，就会离开循环，执行return -1;
//注意这里必须取等，因为arr[right]可能是key值
while (left
//我们arr[mid]已经与key比较过了，所以left需要跳到mid + 1的位置
left = mid + 1;
}
else if (arr[mid] > key)
{
//同上
right = mid - 1;
}
else
{
//这里就是arr[mid] == key的情况
return mid;
}
}
return -1;
}
int main()
{
int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };
int sz = sizeof(arr) / sizeof(arr[0]);
int key = 3;
printf("需要查找的key的下标是%d\n", Binary_search(arr, sz, key));//3
return 0;
}
还有什么不懂的问题，评论区，私信问我吧~~~
|