每日一算二分查找

48次阅读

共计 615 个字符,预计需要花费 2 分钟才能阅读完成。

给定一个整形有序数组,如何找出某一整数是否在数组中,以及该整数在数组中对应的下标?

例如:

int[] arr = {1,4,6,11,23}
int target = 11
找出 target 在 arr 中对应位置的下标
结果是:index = 3

这是一个典型的二分查找问题,代码如下:

public class Solution_1 {private static int findTargetIndex(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {// int mid = (right+left)/2 可能引起溢出问题
int mid = (right - left) / 2 + left;
if (nums[mid] == target) {return mid;}
if (nums[mid] > target) {right = mid - 1;} else {left = mid + 1;}
}
return -1;
}
public static void main(String[] args) {int[] arr = new int[10000000];
for (int i = 0; i < 10000000; i++) {arr[i] = i;
}
int target = 111111;
int targetIndex = findTargetIndex(arr, target);
System.out.println("targetIndex =" + targetIndex);
}
}

正文完
 0