已知一个长度为2015的整型数组,数组里的数据的大小为递增关系,请编写一个函数找到数组中值为2015的数,并返回该数在数组中的位置,未找到则返回-1。
第一种方法:直接从头到尾遍历一次数组即可,时间复杂度为O(n)
第二种方法:二分查找法,时间复杂度为O(logn)
有思路了,写代码就比较简单了,就这
int position(int a[2015])
{
int k = 2015;
int low, high, mid;
low = 0;
high = 2015 - 1;
while (low <= high) {
mid = (low + high) / 2;
if (k > a[mid]) {
low = mid + 1;
}
if (k < a[mid]) {
high = mid - 1;
}
if (k == a[mid]) {
//从第1位开始算的位置
return (mid + 1);
//从第0位开始算的位置
//return mid;
}
}
return -1;
}