【算法例题】二分查找的变形问题
二分查找可以达到log(n)级别的速度，可以快速找到给定的值，当然前提是要排序数组。但二分查找书写过程中会出现边界、死循环问题，还会有变形的二分查找，能正确书写二分查找算法还是有难度的。
1
常规二分查找
常规的二分查找：
1public int bsearch(int[] data , int value) {
2 int n = data.length;
3 int low = 0 , high = n - 1;
4 while (low <= high) {
5 int mid = (high + low)/2;
6 if (data[mid] == value) {
7 return mid;
8 } else if (data[mid] < value) {
9 low = mid + 1;
10 } else {
11 high = mid - 1;
12 }
13 }
14 return -1;
15 }
有两个注意问题，一个while循环条件，另一个是low、high的移动。
2
二分查找的变形问题
1、查找第一个值等于给定值的元素
1public int bsearch(int[] data , int value) {
2 int n = data.length;
3 int low = 0 , high = n - 1;
4 while (low <= high) {
5 int mid = (high + low)/2;
6 if (data[mid] == value) {
7 //判断是不是第一个等于给定值的元素
8 if (mid == 0 || data[mid - 1] != value) {
9 return mid;
10 } else {
11 high = mid - 1;
12 }
13 } else if (data[mid] < value) {
14 low = mid + 1;
15 } else {
16 high = mid - 1;
17 }
18 }
19 return -1;
20 }
在mid处元素等于value情况下，要判断是不是数组第一个元素或者前一个元素和value不等，从而筛选出来。
2、查找最后一个值等于给定值的元素
1public int bsearch(int[] data , int value) {
2 int n = data.length;
3 int low = 0 , high = n - 1;
4 while (low <= high) {
5 int mid = (high + low)/2;
6 if (data[mid] == value) {
7 //判断是不是第一个等于给定值的元素
8 if (mid == n - 1 || data[mid + 1] != value) {
9 return mid;
10 } else {
11 low = mid + 1;
12 }
13 } else if (data[mid] < value) {
14 low = mid + 1;
15 } else {
16 high = mid - 1;
17 }
18 }
19 return -1;
20 }
和第一个异曲同工。
3、查找第一个大于等于给定值的元素
1public int bsearch(int[] data , int value) {
2 int n = data.length;
3 int low = 0 , high = n - 1;
4 while (low <= high) {
5 int mid = (high + low)/2;
6 if (data[mid] < value) {
7 low = mid + 1;
8 } else {
9 if (mid == 0 || data[mid - 1] < value) {
10 return mid;
11 } else {
12 low = mid + 1;
13 }
14 }
15 }
16 return -1;
17 }
只需要在mid处的值大于等于value情况下判断，看此时mid是否是0或者前一个数比value下小。
4、查找最后一个小于等于给定值的元素
1public int bsearch(int[] data , int value) {
2 int n = data.length;
3 int low = 0 , high = n - 1;
4 while (low <= high) {
5 int mid = (high + low)/2;
6 if (data[mid] > value) {
7 low = mid + 1;
8 } else {
9 if (mid == n - 1 || data[mid + 1] > value) {
10 return mid;
11 } else {
12 low = mid + 1;
13 }
14 }
15 }
16 return -1;
17 }
此时就是在mid处值小于等于value下判断。
3
应用