折半查找

    通过折半查找的方法 进行查找元素的时候：

 

必须要保证要查找的元素集合collection是有序的。然后想象改需要查找的集合是有头又尾的，头为top,尾bottom.

 

（1）先把要查找的目标元素target，同集合的中间元素mid进行比较。

（2）如果target>collection[mid]则表示,目标元素在集合的右半部分中，因此【top=mid+1】。

（3）否则目标元素在左半部分，因此【bottom=mid-1】。

（4）然后重复这个过程，直到target==data[mid]--->>元素找到,或者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[mid]) {
				bottom = mid - 1;

			} else if (target>data[mid]) {
				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[mid]){
	    
		return binarySearch(target,mid+1,end,arr);
	   }else if(target<arr[mid]){
	     
		 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 楼 tomoya 2010-12-03  

int mid = (top + bottom) / 2; 容易越界
可以这样：

int mid = bottom+ ((top - bottom) / 2);
或者
int mid = (bottom+ top ) >>> 1;