共计 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); | |
} | |
} |
正文完