二分查找、添加、删除操作详解

你的名字 2022-05-15 03:09 121阅读 0赞

package binary\_search;

/\*\*  
 \* @author 周艺  
 \*\*/

public class binary\_search \{  
    private long\[\] a;// 这个是一个数组  
    private int nElems;// 数据量，数据元素个数  
    // 构造函数

public binary\_search(int max) \{  
        a = new long\[max\];// 创建这个数组、并且给赋值的最大值  
        nElems = 0;// 数据量为0  
    \}

// 为了查看数据大小，元素的个数  
    public int size() \{  
        return nElems;  
    \}

// 二分查找  
    public int find(long searchKey) \{  
        int lowerBound = 0;// 定义一个最小的  
        int upperBound = nElems - 1;// 定义一个最大的  
        int curIn;// 中间项  
        while (true) \{  
            curIn = (lowerBound + upperBound)/ 2;// 先求出中间项  
            if (a\[curIn\] == searchKey)// 如果刚好等于返回  
                return curIn;  
            else if (lowerBound > upperBound)  
                return nElems;// 返回最大的索引数  
            else \{// 继续找  
                if (a\[curIn\] < searchKey)   
                    // 往后面找  
                    lowerBound = curIn + 1;  
                 else   
                    upperBound = curIn - 1;  
                  
            \}  
        \}

// 添加数据项  
    public void insert(long value) \{  
        int j;  
        // 因为是有序的，所以我从0开始查找  
        for (j = 0; j < nElems; j++)   
            if (a\[j\] > value) // 如果数组里的值，比我输入的值要大的话，那么就不需要再往下了，所以取前面的数据就可以了的。  
                break;  
            // 如果确定所插入的值的位置以后，我先调整后面数组中元素的位置，也就是向后移动。  
            // 让k等于最大个数，就是从最后面开始移动，循环成立的条件是k>j  
            for (int k = nElems; k > j; k--)  
                a\[k\] = a\[k - 1\];// 如果觉得不好理解，你可以这样理解：之前是在k-1为位置，现在是由k位置变成了k的位置，那么中间肯定是多了一个  
                a\[j\] = value;// 再把这个值value放到j位置中  
                nElems++;// 数据总量是要增加的  
        \}  
          
    // 删除数据项  
    public boolean delete(long value) \{  
        // 在进行删除之前，首先我要判断你也删除的这个数到底在不在数组里面，也就是用到了上面的二分查找  
        int j = find(value);// 定义获得值  
        if (j == nElems) \{//如果等于数据总量  
            return false;  
        \} else \{  
            for (int k = j; k < nElems; k++)  
                a\[k\] = a\[k + 1\];  
            nElems--;  
            return true;  
        \}  
    \}  
      
    // 显示所有数据项  
    public void display() \{  
        for (int j = 0; j < nElems; j++) \{  
            System.out.print(a\[j\] + " ");  
        \}  
        System.out.println();//换行输出  
    \}

再写个测试类：

package binary\_search;

public class Test \{

public static void main(String\[\] args) \{  
        // TODO Auto-generated method stub  
        int maxSize=100;  
        binary\_search arr;  
        arr=new binary\_search(maxSize);  
        arr.insert(77);  
        arr.insert(99);  
        arr.insert(44);  
        arr.insert(55);  
        arr.insert(22);  
        arr.insert(88);  
        arr.insert(11);  
        arr.insert(00);  
        arr.insert(66);  
        arr.insert(33);  
          
        //插入的数据  
        int searchKey=44;  
        if(arr.find(searchKey)!=arr.size())\{//如果返回的索引不等于数据量的大小，那么就证明已经找到了  
            System.out.println("Found"+searchKey);  
        \}else\{  
            System.out.println("Can't find "+searchKey);  
        \}  
          
        //调用显示  
        arr.display();  
        //删除  
        arr.delete(00);  
        arr.delete(55);  
        arr.delete(99);  
        //调用显示  
        arr.display();