二分查找:根据索引二分,循环查找的条件是左索引小于等于右索引。
二叉树需要判断自身根是否为NULL,并通过改变current的值进行判断。
#include <iostream>
using namespace std;
// 长度为 N 的有序表nums 中查找 target
int BiSearch(int *nums, int N, int target)
{
int l = 0, r = N - 1;
while (l <= r)
{
int mid = (l + r) / 2;
if (target == nums[mid])
{
return mid;
}
if (target < nums[mid])
{
r = mid - 1;
}
if (target > nums[mid])
{
l = mid + 1;
}
}
return -1;
}
// 二叉树
typedef struct TreeNode
{
int data;
struct TreeNode *left, *right;
} TreeNode;
TreeNode *SearchTree(TreeNode *root, int target)
{
if (!root)
{
return NULL;
}
TreeNode *current = root;
while (current)
{
if (target == current->data)
{
return current;
}
if (target < current->data)
{
current = current->left;
}
else
{
current = current->right;
}
}
return NULL;
}
int main()
{
int nums[10] = {
1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
cout << BiSearch(nums, 10, 5) << endl;
return 0;
}