折半查找(二分搜索)的应用和技巧全面总结

《折半查找(二分搜索)的应用和技巧全面总结》由会员分享，可在线阅读，更多相关《折半查找(二分搜索)的应用和技巧全面总结（6页珍藏版）》请在金锄头文库上搜索。

1、折半查找（二分搜索）的应用和技巧全面总结折半查找（二分搜索）的应用和技巧全面总结折半查找应该算是算法中比较简单常见，但却很实用的方法之一了，又叫做二分搜索，其应用比较广泛，可以用于排序数组中元素的查找，复杂度仅为 log（N），也可以用于有序数组中插入元素等等，一般而言针对排序数组的一些算法都会活多或少的用到折半查找活折半查找的思想，折半查找的实现主要分为两种方式，一种是遍历非递归形式，一种是采用递归的形式。1、非递归形式，这种实现主要是通过每次调整中点的位置来实现。1. int binsearch1(int arr, int k, int l, int h) 2. if(l h) 3. re

2、turn -1; 4. 5. int mid; 6. while(l arrmid) 11.l = mid + 1; 12.else 13.h = mid - 1; 14. 15. 16.return -1; 17. 这种方式比较灵活，而已有利于解决很多变形的问题，后面会介绍。2、递归的形式，这种形式比较简单，调整起点，中点，终点的位置，递归函数就可以实现1. int binsearch2(int arr, int k, int l, int h) 2. if(l h) 3. return -1; 4. 5. int mid = (l + h) / 2; 6. if(k = arrmid) 7

3、. return mid; 8. else if(k arrmid) 9. binsearch2(arr, k, mid +1, h); 10.else if(k arrm) 6. l = m; 7. else 8. h = m; 9. 10. 11.int p = h; 12.if(p = n | arrp != k) 13.return -1; 14. 15.return h; 16. 算法分析：设定两个不存在的元素 a-1和 an，使得 a-1 l=-1, (l+u)/2 al 3. while(l + 1 != h) 4. int m = (l + h) / 2; 5. if(k =

4、arrm) 6. l = m; 7. else 8. h = m; 9. 10. 11.int p = l; 12.if(p aleft, 则 right=mid-1；其他情况，left =mid+1；如果右边是有序的，若 x amid 且 x= alow) /数组左半有序 9. if (t = alow 4. 5. int mid; 6. while(l arrmid) 11.l = mid + 1; 12.else 13.h = mid - 1; 14. 15. 16.return l; 17. 五、二分思想的变形，其实二分是一种思想，不单单是应用于有序序列，可以应用于很多将序列进行划分的问题上。