#include <stdio.h>
int BinarySearch(int* Nums, int Size, int Left, int Right, int Target);
void test(void);
int main()
{
test();
return 0;
}
void test(void) {
int a[10] = { 3,7,14,17,17,23,27,29,45,67 };
int find=BinarySearch(a, 10, 0, 9, 23);
printf("%d\n", find);
find = BinarySearch(a, 10, 0, 9, 3);
printf("%d\n", find);
find = BinarySearch(a, 10, 0, 9, 67);
printf("%d\n", find);
}
int BinarySearch(int* Nums, int Size, int Left, int Right, int Target) {
int L = Left; int R= Right;
while (L<=R)
{
int mid = (L + R) / 2;
if (Nums[mid] == Target)
return mid;
else if (Nums[mid] > Target) {
R=mid-1;
}
else {
L=mid+1;
}
}
if (L > R)return -1;
}
image.png
容易错的地方，R=mid-1,L=mid+1
假设有个数组a[3,5,7]，查找7；第一次L=0,R=2,mid=1,a[1]=5，5<7;
第二次查找，如果让L=mid=1,在[5,7]内查找，那这次的mid=(1+2)/2=1,就会找不到
循环条件为什么是L<=R,二分查找分到最后可能会剩一个元素，这时 L=R;
如果最后那次(L=R)循环还没找到，不管R=mid-1还是L=mid+1（这里的mid=L=R），都会让L>R，返回-1表示没有找到
