二分查找你针对有序序列而言的一种查找算法,关于二分查找有一下的几类问题:
1. 给定一个有序(不降序)数组arr,求任意一个i使得arr[i]等于v,不存在则返回-1
2.给定一个有序(不降序)数组arr,求最小的i使得arr[i]等于v,不存在则返回-1
3.给定一个有序(不降序)数组arr,求最大的i使得arr[i]等于v,不存在则返回-1
4.给定一个有序(不降序)数组arr,求最大的i使得arr[i]小于v,不存在则返回-1
5.给定一个有序(不降序)数组arr,求最小的i使得arr[i]大于v,不存在则返回-1
注意的是:
1,在求二分查找的中间点时没有使用
midIndex = (minIndex + maxIndex) / 2
是因为,以免 minIndex + maxIndex之后会导致溢出而出现错误。
2,注意循环的循环终止条件及边界元素的判定
#include <stdlib.h> #include <string.h> #include <stdio.h> /* //给定一个有序(不降序)数组arr,求最大的i使得arr[i]等于v,不存在则返回-1 int bisearch(char arr[][10], int begin, int end, char *v) { int minIndex = begin; int maxIndex = end; int midIndex; while(minIndex < maxIndex - 1) { midIndex = minIndex + (maxIndex - minIndex) / 2; if(strcmp(arr[midIndex], v) <= 0) minIndex = midIndex; else maxIndex = midIndex; } if(!strcmp(arr[maxIndex], v)) return maxIndex; else if(!strcmp(arr[minIndex], v)) return minIndex; else return -1; } */ /* //一个有序(不降序)数组arr,求任意一个i使得arr[i]等于v,不存在则返回-1 int bisearch(char (*arr)[10], int begin, int end, char *v) { int minIndex = begin; int maxIndex = end; int midIndex; while(minIndex < maxIndex) { midIndex = minIndex + (maxIndex - minIndex) / 2; if(strcmp(*(arr + midIndex), v) < 0) minIndex = midIndex + 1; else if(strcmp(*(arr + midIndex), v) > 0) maxIndex = midIndex - 1; else return midIndex; } if(!strcmp(*(arr + minIndex), v)) return minIndex; return -1; } */ /* //给定一个有序(不降序)数组arr,求最小的i使得arr[i]等于v,不存在则返回-1 int bisearch(char (*arr)[10], int begin, int end, char *v) { int minIndex = begin; int maxIndex = end; int midIndex; while(minIndex < maxIndex - 1) { midIndex = minIndex + (maxIndex - minIndex) / 2; if(strcmp(*(arr + midIndex), v) < 0) minIndex = midIndex; else maxIndex = midIndex; } if(!strcmp(*(arr + minIndex), v)) return minIndex; else if(!strcmp(*(arr + maxIndex), v)) return maxIndex; else return -1; } */ /* //给定一个有序(不降序)数组arr,求最大的i使得arr[i]小于v,不存在则返回-1 int bisearch(char (*arr)[10], int begin, int end, char *v) { int minIndex = begin; int maxIndex = end; int midIndex; while(minIndex < maxIndex - 1) { midIndex = minIndex + (maxIndex - minIndex) / 2; if(strcmp(*(arr + midIndex), v) < 0) minIndex = midIndex; else maxIndex = midIndex; } if(strcmp(*(arr + maxIndex), v) < 0) return maxIndex; else if(strcmp(*(arr + minIndex), v) < 0) return minIndex; else return -1; } */ //给定一个有序(不降序)数组arr,求最小的i使得arr[i]大于v,不存在则返回-1 int bisearch(char (*arr)[10], int begin, int end, char *v) { int minIndex = begin; int maxIndex = end; int midIndex; while(minIndex < maxIndex - 1) { midIndex = minIndex + (maxIndex - minIndex) / 2; if(strcmp(*(arr + midIndex), v) <= 0) minIndex = midIndex; else maxIndex = midIndex; } //从小数开始判断 if(strcmp(*(arr + minIndex), v) > 0) return minIndex; else if(strcmp(*(arr + maxIndex), v) > 0) return maxIndex; else return -1; } int main() { char a[][10] = {"abc", "bcd", "bddaaa", "ddcd", "ddd", "ddd", "ddd", "ddd", "xxx", "xxx"}; char v[] = "zzz"; int last = sizeof(a) / (sizeof(char) * 10); int index = bisearch(a, 0, last-1, v); printf("index of v is %d\n", index); return 0; }