java二分算法出现错误

Question

Java版二分查找:

package com.binarySearch.binarySearch;

public class BinarySearch_Balance {

    static int binarySearch_Balance(int[] arr, int target){
        if (target<arr[0] || target> arr[arr.length -1]) //如果目标在超出容器范围就不必寻找
            return -1;
        int left = 0;
        int right = arr.length;
        while(left < right){
            int middle = ((left + right) >>> 1);
            if(target < arr[middle])
                right = middle;
            else
                left = middle + 1;
        }
        return (arr[left] == target ? left : -1);
    }

    public static void main(String[] args) {
        int[] arr = {-1, 1, 7, 15, 23, 33, 88, 109};
        int res = binarySearch_Balance(arr, 15);
        if(res != - 1)
            System.out.printf("target(%d) has been found", res);
        else
            System.out.println("no target");
    }
}

C++版二分查找

#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
    static int search(vector<int>& nums, int target) {
            if (target<nums[0] || target>*(nums.end() - 1)) //如果目标在超出容器范围就不必寻找
                return -1;

        int i = 0; //头指针
        int j = nums.size(); //尾指针

        while (i < j) {
            int m = (i + j) >> 1; //中间值
            if (nums[m] < target)
                i = m + 1;
            else
                j = m;
        }
        return (nums[i] == target ? i : -1);
    }
};

int main() {
    vector<int> nums = {-1,2,4,5,7,9,11,34,55,67 };
    int index = Solution::search(nums, -2);
    if (index != -1) {
        cout << nums[index] << endl;
    }
    else {
        cout << "Target not found" << endl;
    }

    return 0;
}

为什么java版输出始终是"no target"?, C++版却能够成功

Answer 1

让阿豪来帮你解答，本回答参考chatgpt3.5编写提供，如果还有疑问可以评论或留言

Java版二分查找的输出始终为"no target"是因为在进行二分查找时，在找到target值时，返回的是left的值，而不是target的索引，因此需要将返回值arr[left]与target进行判断，如果相等，说明target在数组中存在，返回left的值作为target的索引，否则返回-1。修改代码如下：

static int binarySearch_Balance(int[] arr, int target){
    if (target<arr[0] || target> arr[arr.length -1]) //如果目标在超出容器范围就不必寻找
        return -1;
    int left = 0;
    int right = arr.length;
    while(left < right){
        int middle = ((left + right) >>> 1);
        if(target < arr[middle])
            right = middle;
        else
            left = middle + 1;
    }
    return (left > 0 && arr[left - 1] == target ? left - 1 : -1);
}

C++版二分查找成功的原因也是因为返回的是target的索引，而不是left的值。代码中直接返回i的值作为target的索引，因此不需要额外的判断。