查找算法·折半查找

本文主要是介绍查找算法·折半查找，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

算法讲解请参阅下面参考书籍，这里只给出自己练习时的代码实现。
参考书籍：《算法设计与分析基础·3ed》

1.伪代码

算法: BinarySearch(A[0...n-1], K)//实现非递归的折半查找//输入：一个升序数组A[0...n-1]和一个待查找元素K//输出：如果元素存在，则输出查找元素所对应的数组下标；如果没有，则返回-1l = 0; r = n-1;while l <= r dom = ⌊(l+r)/2⌋if K = A[m] return melse if K < A[m] r = m-1else l = m+1return -1

2.CPP实现：

#include <iostream>using namespace std;int binary_search(int arr[], int length, int K);int main()
{int arr[] = {5, 10, 15, 20, 25, 30, 35, 40, 45, 50};int length = sizeof(arr) / sizeof(int);int id =  binary_search(arr, length, 45);cout << "id:" << id << endl;return 0;
}int binary_search(int arr[], int length, int K)
{int n = length;int l = 0;int r = n - 1;while(l <= r){int m = (int) (l+r) / 2;if(K == arr[m])return m;else if(K < arr[m]) r = m-1;else l = m+1;}return -1;
}

3.算法复杂度：
输入规模：n
基本操作：三路数值比较
复杂度：

这篇关于查找算法·折半查找的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---