由于春节期间摸鱼太多,导致重拾学习变得十分艰难,假期计划全部被打乱(不愧是我)。从今天开始继续算法的学习。

原理

  • 查找范围每次缩小一半
  • 仅对有序排列的数据有效

实现

标准二分查找

在按从小到大排列、有size个元素的整形数组中查找元素num。若找到,返回num的下标,若无法找到,返回-1。
代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int BinarySearch(int array[],int size,int num){
int L = 0;
int R = size-1; //确定查找区间左右端点
while(L <= R){ //若查找区间不为空 则继续查找
int mid = L+(R-L)/2; //确定区间中点(整数除法)
if(num == array[mid])
return mid;
else if(num > array[mid])
L = mid + 1; //更新区间左端点
else
R = mid - 1; //更新区间右端点
}
return -1;
}

查找比指定元素小的元素中下标最大的那个元素

在按从小到大排列、有size个元素的整形数组arrary中查找比元素num小的、下标最大的元素。若找到,返回其下标,若无法找到,返回-1。
代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int LowerBound(int array[],int size,int num){
int L = 0;
int R = size-1; //确定查找区间左右端点
int last_Position = -1; //初始化下标
while(L <= R){ //若查找区间不为空 则继续查找
int mid = L+(R-L)/2; //确定区间中点
if(array[mid] >= num)
R = mid - 1; //更新区间右端点
else{
last_Position = mid; //更新下标
L= mid + 1; //更新区间左端点
}
}
return last_Position;
}

如何取查找区间中点下标?

  • int mid = (Left + Right)/2

防止(Left + Right)溢出:

  • int mid = Left + (Right - Left)/2