二分查找

一组排序数中，给定一个数，返回最接近且不大于这个数的位置.要求时间复杂度在O(logn）

    public int getIndex(int[] a,int data){
        int left=0;
        int right=a.length-1;
        while(left<=right){
            int mid=left+(right-left)/2;
            if(a[mid]== data){
                return mid;
            }
            else if(a[mid] <data){
                 left=mid+1;
            }
            else{
                right=mid-1;
            }
        }
        return left-1;
    }

给定一个整型数组和一个整数，要找出数组中的两个数字，使得这两个数字的和等于给定的和。

例如，输入数组numbers={1,2,3,4,5,6,7}，给定和为9，则要找出2和7，3和6，4和5的位置
给一个无序数组int[] nums 和一个整数 target，在这个数组中找到两个数 ，使得这个两个数的和等于target，找到这个数组中所有的满足这样条件的数
无序数组，给出O(N)时间复杂度的算法

public List getAll(int[] a,int target){
        Map<Integer,Integer> map=new HashMap<>();
        List list=new ArrayList<>();
        for(int i=0;i<a.length;i++){
            if(map.containsKey(a[i])){
                //int[] arrIndex=new int[2];
                int index=map.get(a[i]);
                List tmplist=new ArrayList<>();
//              arrIndex[0]=index;
//              arrIndex[1]=i;
                tmplist.add(index);
                tmplist.add(i);
                list.add(tmplist);
                
            }
            else{
                map.put(target-a[i], i);
            }
        }
        return list;
    }

有序数组，o(logn)的算法

public List<List> getAllSortedArray(int[] a,int target){
        int left=0;
        int right=a.length-1;
        List list=new ArrayList<>();
        while(left<right){
            int sum=a[left]+a[right];
            if(sum==target){
                List tempList=new ArrayList();
                tempList.add(left);
                tempList.add(right);
                list.add(tempList);
                left=left+1;
                right=right-1;
                
            }
            else if(sum>target){
                right=right-1;;
            }
            else{
                left=left+1;
            }
            
        }
        return list;
    }