先上代码
//查找value对应下标，找不到返回-1
int binarySearch(int arr[], int length, int value) {
int middle, low, high;
low = 0;
high = length - 1;
while(low <= high) {
middle = low + ((high - low) >> 1);
if (arr[middle] == value)
{
return middle;
} else if(arr[middle] > value) {
high = middle - 1;
} else {
low = middle + 1;
}
}
return -1;
}
时间复杂度: log(n)
二分查找只能作用在有序数组中
核心思想
取出数组最中间的数，与要查找的值做比较，会有如下3种情况。
- 中间数等于查找数 直接返回下标
- 中间数大于查找数，说明要查找的数只可能出现在中间数的左边。
- 中间数小于查找树，说明要查找的数只可能出现在中间数的右边。
有了上面三种情况，我们就可以不断缩小查找范围。
直至找到查找数，或者取得查找数不存在数组中。
一步一步实现二分查找
定义中间数下标，起始下标。
int binarySearch(int arr[], int length, int value) {
//中间 开始 结束
int middle, low, high;
low = 0;
high = length - 1;
}
终止条件
int binarySearch(int arr[], int length, int value) {
//中间 开始 结束
int middle, low, high;
low = 0;
high = length - 1;
//low 如果大于 high 说明查找数不存在数组中
while(low <= high) {
}
return -1;
}
计算中间数下标,判断中间数的大小
int binarySearch(int arr[], int length, int value) {
//中间 开始 结束
int middle, low, high;
low = 0;
high = length - 1;
//low 如果大于 high 说明查找数不存在数组中
while(low <= high) {
//中间数的下标
middle = low + ((high - low) >> 1);
//判断中间数与查找数的关系
if(arr[middle] == value) {
//相等就直接返回下标
return middle;
} else if (arr[middle] > value) {
//大于就说明查找数可能出现在中间数左边，减小high
high = middle - 1;
} else {
//小于就说明查找数可能出现在中间数右边，加大low
low = middle + 1;
}
}
return -1;
}
二分查找代码到这就完成了是不是很简单，但是一定要注意细节啊
都看到这了，点个赞再走啊~
