publicclassBinarySearch{ /* * 在有序数组中寻找一个整数 * @param nums,有序数组 * @param target,需要寻找的目标 * @return 找到的数值索引,未找到返回 -1 * */ publicstaticintbinarySearchNum(int[] nums, int target){ int left = 0, right = nums.length - 1; // 搜索区间为 [left, right] while (left <= right) {//重点:因为左右闭区间,所以当 left == right 时,还有一个值需要判断,需要加上等号 int mid = left + (right - left) / 2; if (nums[mid] == target) { return mid; } elseif (nums[mid] < target) { left = mid + 1; //搜索区间变成[mid + 1, right] } else { right = mid - 1; //因为右闭区间,搜索区间为[left, mid - 1] } } return -1; }
publicstaticintbinarySearchNum2(int[] nums, int target){ int left = 0, right = nums.length; // 搜索区间为 [left, right) while (left < right) { //左闭右开区间,当 left == right 时,区间内已经没有值 int mid = left + (right - left) / 2; if (nums[mid] == target) { return mid; } elseif (nums[mid] < target) { left = mid + 1;//搜索区间变成[mid + 1, right) } else { //因为右开区间,搜索区间为[left, mid),如果为 right = mid - 1, //区间为[left, mid - 1),我们会漏掉 mid - 1位置的值 right = mid; } } return -1; }
publicstaticvoidmain(String[] args){ int[] nums = newint[]{2,2,4,5,3,77,44,33,77,2,3,1,14,100}; Arrays.sort(nums); System.out.println(Arrays.toString(nums)); for(int i = 0; i < 5; i++){ Random random = new Random(i*80); int num = nums[random.nextInt(14)]; System.out.println("left <= right: searching " + num + " index: " + binarySearchNum(nums,num)); System.out.println("left < right: searching " + num + " index: " + binarySearchNum2(nums,num)); } } }
输出
1 2 3 4 5 6 7 8 9 10 11
[1, 2, 2, 2, 3, 3, 4, 5, 14, 33, 44, 77, 77, 100] left <= right: searching 77 index: 12 left < right: searching 77 index: 11 left <= right: searching 3 index: 4 left < right: searching 3 index: 5 left <= right: searching 100 index: 13 left < right: searching 100 index: 13 left <= right: searching 3 index: 4 left < right: searching 3 index: 5 left <= right: searching 1 index: 0 left < right: searching 1 index: 0
num[mid] == target 时,我们已经找到了一个值的下标,直接返回即可。
关于 left <= right 和 left < right
当初始化 left = 0, right = nums.length - 1 时,搜索区间为[left, right],当 left == right时,搜索区间内还有一个值 nums[left] 没有判断,循环条件内使用 left <= right,如果使用 left < right 最后需要加一次判断 nums[left] == target ?
当初始化 left = 0, right = nums.length 时,搜索区间为[left, right),当 left == right时,搜索区间内没有值,循环条件内使用 left < right。
v1.5.2