题目描述
假设一个单调递增的数组里的每个元素都是整数并且是唯一的。请编程实现一个函数，找出数组中任意一个数值等于其下标的元素。例如，在数组{-3,-1, 1,3,5}中，数字3和它的下标相等。
思路分析
还是二分查找的思路，如果比较mid和其对应下标的关系：
- 如果大于下标，则查找左边部分；
- 如果小于下标，则查找右边部分；
- 如果正好相等，返回该值；
测试用例
- 功能测试：数组中包含或者不包含数值和下标相等的元素。
- 边界值测试：数组中只有一个数字;数值和下标相等的元素位于数组的开头或者结尾。
- 特殊输入测试：表示数组的指针为nullptr指针。
Java代码
public class Offer053_03 {
public static void main(String[] args) {
test1();
test2();
test3();
}
public static int GetNumberSameAsIndex(int[] array) {
return Solution1(array);
}
private static int Solution1(int[] array) {
if(array==null || array.length<=0) {
return -1;
}
int left = 0;
int right = array.length-1;
while(left<=right) {
int mid = (left+right)>>1;
if(array[mid]>mid) {
right = mid-1;
}else if(array[mid]<mid){
left = mid+1;
}else {
return mid;
}
}
return -1;
}
private static void test1() {
int[] array = {-3,-1, 1,3,5};
System.out.println(GetNumberSameAsIndex(array));
}
private static void test2() {
int[] array = {0,1,2,3,4,5};
System.out.println(GetNumberSameAsIndex(array));
}
private static void test3() {
int[] array = {0};
System.out.println(GetNumberSameAsIndex(array));
}
}