java - ArrayList 上的递归二分查找

Question

我正在尝试对 ArrayList 进行递归二分搜索，但不确定我的代码存在什么问题。我有一个文本文件，其中包含一堆整数，如下所示:

217 320 550 212 12 17 号 3560 2999 211

问题是，当我输入一个数字来搜索ArrayList时，它总是说该元素不存在，但我知道它存在!

        public static int binarySearch(List<Integer> arr, Integer l, Integer r, Integer x)
        {
            if (r>=l)
            {
                Integer mid = l + (r - l)/2;

                // If the element is present at the middle itself
                if ((arr.size()/2) == x)
                    return mid;

                // If element is smaller than mid, then it can only
                // be present in left subarray
                if ((arr.size()/2) > x)
                    return binarySearch(arr, l, mid-1, x);

                // Else the element can only be present in right
                // subarray
                return binarySearch(arr, mid+1, r, x);
            }
            // We reach here when element is not present in array
            return -1;
        }   
    }

任何帮助将不胜感激，新程序员!

Answer 1

检查元素是否存在的部分是错误的，不要这样做:

arr.size()/2 == x
arr.size()/2 > x

相反，请执行以下操作:

arr.get(mid) == x
arr.get(mid) > x

因为您应该访问 mid 位置的元素，而不检查列表大小的一半是否等于 x。