折半查找
通过折半查找的方法 进行查找元素的时候：必须要保证要查找的元素集合collection是有序的。然后想象改需要查找的集合是有头又尾的，头为top,尾bottom.
（1）先把要查找的目标元素target，同集合的中间元素mid进行比较。
（2）如果target>collection则表示,目标元素在集合的右半部分中，因此【top=mid+1】。
（3）否则目标元素在左半部分，因此【bottom=mid-1】。
（4）然后重复这个过程，直到target==data--->>元素找到,或者top>bottom,元素未找到。
JAVA代码实现(非递归):
public class BiFind {// 假如data[]数组是从小到大的public static boolean find(int[] data, int target) {int top = 0;int bottom = data.length - 1;while (top <= bottom) {int mid = (top + bottom) / 2;if (target < data) {bottom = mid - 1;} else if (target>data) {top = mid + 1;} else {return true;}}return false;}public static void main(String[] args) {int[] data = new int[] { 1, 2, 3, 4, 5,5,5,5,6, 6, 6,11111 };System.out.println(find(data, 5));}}
C代码实现【VC2005运行成功】:
改用C语言实现了一下，先对无序数组进行冒泡排序(bubble sort),然后再进行二分查找(递归实现)。
#include "stdafx.h"int binarySearch(int target,int start,int end,int* arr);void bubbleSort(int* arr,int length);int main(){int a[]={1,233,3,4,5,6,337,811,9,10}; int length = sizeof(a)/sizeof(int);int target = 10;bubbleSort(a,length);if(binarySearch(target,0,length-1,a)>0){printf("target %d is found",target);} return 0;}int binarySearch(int target,int start,int end,int* arr){ int mid = (start+end)/2; if(start>end) return -1; if(start<=end){ if(target>arr){ return binarySearch(target,mid+1,end,arr); }else if(target<arr){ return binarySearch(target,start,mid-1,arr); }else{ return mid; } }}void bubbleSort(int* arr,int length){for(int i=0;i<length;i++){ bool exchange = false; //小心指针越界，j<length-1 for(int j=0;j<length-1;j++){ int temp = 0;if(*(arr+j)>*(arr+j+1)){ temp=*(arr+j); *(arr+j) = *(arr+j+1); *(arr+j+1) = temp; exchange =true;} } if(!exchange) {break;}}}
页:
[1]