求教二分法原理

这就1个分了？

不知道你说的可是二分法查找;
对于二分法查找的话它是需要有前提条件的,那就是原本的数据是需要已经排好序的;
假设原数据集合降序排列,对于这个已经排好序的大型数据集合每次都折半,取中间的值m和和目标值n进行比较,如果m>n,则在m的右边继续折半并和n进行比较,反之则在m的左边进行折半和n对比,直到找到n

这是我的理解 ,希望可以能帮上你

折半排序法、也就是二分排序法
通过不断取中间值进行比较来进行排序
他是不断的利用中间值跟你所需要的值来进行比较，然后通过大小，不断的该变最大值和最小值
然后从新定义中间值，是的查找范围越来越小，直到跟你所要找的值相匹配，然后停止

//        二分查找的基本思想
//       　二分查找的基本思想是：（设R[low..high]是当前的查找区间）
//    （1）首先确定该区间的中点位置：
//                     
//    （2）然后将待查的K值与R[mid].key比较：若相等，则查找成功并返回此位置，否则须确定新的查找区间，继续二分查找，具体方法如下：
//      　 ①若R[mid].key>K，则由表的有序性可知R[mid..n].keys均大于K，因此若表中存在关键字等于K的结点，则该结点必定是在位置mid左边的子表R[1..mid-1]中，故新的查找区间是左子表R[1..mid-1]。
//       　②类似地，若R[mid].key<K，则要查找的K必在mid的右子表R[mid+1..n]中，即新的查找区间是右子表R[mid+1..n]。下一次查找是针对新的查找区间进行的。
//       　因此，从初始的查找区间R[1..n]开始，每经过一次与当前查找区间的中点位置上的结点关键字的比较，就可确定查找是否成功，不成功则当前的查找区间就缩小一半。这一过程重复直至找到关键字为K的结点，或者直至当前的查找区间为空(即查找失败)时为止。
//
//   二分查找算法
       int BinSearch(SeqList R,KeyType K)
         { //在有序表R[1..n]中进行二分查找，成功时返回结点的位置，失败时返回零
           int low=1,high=n,mid; //置当前查找区间上、下界的初值
           while(low<=high){ //当前查找区间R[low..high]非空
             mid=(low+high)/2;
             if(R[mid].key==K) return mid; //查找成功返回
             if(R[mid].kdy>K)
                high=mid-1; //继续在R[low..mid-1]中查找
             else
                low=mid+1; //继续在R[mid+1..high]中查找
            }
           return 0; //当low>high时表示查找区间为空，查找失败
          } //BinSeareh
        

1、算法概念。

二分查找算法也称为折半搜索、二分搜索，是一种在有序数组中查找某一特定元素的搜索算法。请注意这种算法是建立在有序数组基础上的。
2、算法思想。

①搜素过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；

②如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。

③如果在某一步骤数组为空，则代表找不到。

这种搜索算法每一次比较都使搜索范围缩小一半。

3、实现思路。

①找出位于数组中间的值，并存放在一个变量中（为了下面的说明，变量暂时命名为temp）；

②需要找到的key和temp进行比较；

③如果key值大于temp，则把数组中间位置作为下一次计算的起点；重复① ②。

④如果key值小于temp，则把数组中间位置作为下一次计算的终点；重复① ② ③。

⑤如果key值等于temp，则返回数组下标，完成查找。



private static int binarySearch0(int[] a, int fromIndex, int toIndex, int key) {
    int low = fromIndex;
    int high = toIndex - 1;
    while (low <= high) {
        int mid = (low + high) >>> 1;
        int 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.
    }

二分法检索二分法检索要求线性表结点按关键码值排序且以顺序方式存储。在查找时，首先与表的中间位置上结点的关键值比较，若相等则检索成功;否则根据比较结果确定下一步在表的前半部或后半部中继续进行。二分法检索的效率较高，设线性表有n个元素，则最多的检索次数为大于log2 n 的最小整数，最少的检索次数为1。二分法检索又称折半检索，二分法检索的基本思想是设字典中的元素从小到大有序地存放在数组中，首先将给定值key与字典中间位置上元素的关键码比较，如果相等，则检索成功；否则，若key小，则在字典前半部分中继续进行二分法检索，若key大，则在字典后半部分中继续进行二分法检索。这样，经过一次比较就缩小一半的检索区间，如此进行下去，直到检索成功或检索失败。二分法检索是一种效率较高的检索方法，要求字典在顺序表中按关键码排序。  lbN,以2为底的对数，取上限，最多4次。 原理是折半查找，每次把表分成两半，因为已经排序的，所以只需要和中间数比较就能确定是在哪一半，然后不断分成两半，直到匹配，或者没有数字，表示查找失败。次数最多就是上面提到的。

二分法是一种简略说法，其实就是折半查找，属于数据结构中查找排序中的一种，比老师的视频里有讲过这个方法，二分查找的前提条件必须保证你的数组是有序的，然后才能用二分查找，所以你先得将数组进行排序。

1. public static int bSearch(int[] array,int key)
   
2. {
   
3. int low = 0;
   
4. int high = array.length -1;
   
5. int mid;
   
6. while(low <= high)
   
7. {
   
8. mid = (low + high)/2;
   
9. if(array[mid] == key)
   
10. {
    
11. return mid;
    
12. }
    
13. if(array[mid] > key)
    
14. {
    
15. high = mid - 1;
    
16. }
    
17. else
    
18. {
    
19. low = mid + 1;
    
20. }
    
21. }
    
22. return -1;
    
23. }

复制代码

也就是折半查找。定义一个最大值max，最小值min，中间值mid。
mid=(max+min)/2; 如果x>mid，说明x在mid与max之间，将min移动到mid+1；同理，直到找到x位置，这样减少了其他查找方法所需要的次数，所以叫折半查找