请问我自己写了个二分法但超时是哪里的问题

来源:3-6 对撞指针 Two Sum II - Input Array is Sorted

夜的钢琴曲5

2019-10-19

public class TwoSum2 {
            public int[] twoSum(int[] numbers, int target) {
                return binarySearch(numbers,target);
            }
            private int[] binarySearch(int[] arr,int target) {
                int l = 0;
                int r = arr.length;
                int mid = (l + r) / 2;
                int[] index = new int[2];
                for (int i = 0; i < arr.length; i++) {
                    while (l < r) {
                        if (arr[i] + arr[mid] == target) {
                            index[0] = i;
                            index[1] = mid;
                            break;
                        }
                        if (arr[i] + arr[mid] < target)
                            l = mid + 1;
                        if (arr[i] + arr[mid] > target)
                            r = mid - 1;
                    }
                }
                return index;
            }

    public static void main(String[] args) {
        int[] num = {2,7,11,5};
        int t = 9;
        TwoSum2 twoSum2 = new TwoSum2();
        String s =  twoSum2.twoSum(num,t).toString();
        System.out.println(s);
    }
}

波波老师,对于leetcode167题的二分法,我自己写了个办法,但不知道为什么上传的话是超时,然后我写了个测试,但是没返回。而且我debug时只有在打印的那一行标记断点才有意义,但那一行debug也没返回,我反复检查了几次,都没发现逻辑问题,请问代码时哪里有问题呢?

写回答

1回答

liuyubobobo

2019-10-20

首先,你的测试用例有问题。


167 问题保证传入的数组是有序的,二分搜索法也必须在有序数组上运行。你的测试数组不是有序的。


其次,r 的初值应该为 arr.length - 1,请再回顾一下课程的 3-1;3-2 两个小节,理解清楚为什么。


然后,l,r,mid 的定义,应该 for 循环内。每一轮 for 循环,重新运行一遍二分搜索。你将这些二分搜索使用的变量定义在循环外面,上一轮循环改变的 l,r,mid 值会影响下一次二分搜索。


这些问题都修改完以后,对于这个题目,还包含搜索到的索引是相同的问题(如果你将代码修改正确了,提交给 Leetcode,就会明白了),可以思考一下怎么解决?然后,再回顾一下课程给出的参考代码?

https://github.com/liuyubobobo/Play-with-Algorithm-Interview/blob/master/03-Using-Array/Course%20Code%20(Java)/06-Two-Sum-II/src/Solution2.java 


==========


P.S. debug 的意义是要一步一步跟程序。一步一步看,程序走在每一行,数据是如何变化的,和你想要的逻辑是否一致。如果不一致,自己到底哪里想错了。或者为什么无法执行到某个点,为什么执行不下去了。只是打一个断点,是没有意义的。


继续加油!:)

0
1
夜的钢琴曲5
谢谢波波老师指点
2019-10-20
共1条回复

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题,高频算法题解析,强化训练

7408 学习 · 1150 问题

查看课程