数据结构：二分查找与二叉树

妖狐艹你老母 2022-06-03 08:54 224阅读 0赞

*  关于二分查找，原理其实不难，而且java Arrays类里面有一个sorts()方法，可以先对数据进行排序，然后调用binarySerarch()方法，这个方法就是进行二分查找用的。
 *  下面是JDK的源代码：

private static int binarySearch0(long[] a, int fromIndex, int toIndex,
                                         long key) {
            int low = fromIndex;
            int high = toIndex - 1;
    
            while (low <= high) {
                int mid = (low + high) >>> 1;
                long midVal = a[mid];
    
                if (midVal < key)
                    low = mid + 1;
                else if (midVal > key)
                    high = mid - 1;
                else
                    return mid; // key found
            }
            return -(low + 1);  // key not found.
        }

*  说下原理：一个有序数组，需要查找某一个数组中某一个值，二分查找就就是先按照数组下标加一，然后除以二，之后向下取余。也就是数组\{2，3，4\}按照下标算toIndex 最大是二，（2+1）/2 = 1…1直接取1，数组下标为一的数是3。然后我们拿到这个中值a，如果我们要查的值比a这个值小，这时a就变成最大值，再按照上述方式进行循环查找。

--------------------

*  简述一下二叉树的原理：数组拿出一个数作为根节点，把比这个数小的放在左子树上，然后把比这个数打的放在右子树上。以此类推。  
    [http://blog.csdn.net/h348592532/article/details/45741935][http_blog.csdn.net_h348592532_article_details_45741935]

[http_blog.csdn.net_h348592532_article_details_45741935]: http://blog.csdn.net/h348592532/article/details/45741935