詳解二分查找算法

二分查找又稱折半查找，優(yōu)點是比較次數少，查找速度快，平均性能好；其缺點是要求待查表為有序表，且插入刪除困難。因此，折半查找方法適用于不經常變動而查找頻繁的有序列表。首先，假設表中元素是按升序排列，將表中間位置記錄的關鍵字與查找關鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、后兩個子表，如果中間位置記錄的關鍵字大于查找關鍵字，則進一步查找前一子表，否則進一步查找后一子表。重復以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時查找不成功。

前提：數組必須是有序的。

算法時間復雜度：O(log(n))

二分查找法也稱為折半查找法，它充分利用了元素間的次序關系，采用分治策略，可在最壞的情況下用O(log n)完成搜索任務。它的基本思想是，將n個元素分成個數大致相同的兩半，取a[n/2]與欲查找的x作比較，如果x=a[n/2]則找到x，算法終止。如 果x

總之，二分查找算法的思想就跟二叉樹的查找一樣，如果大于就在右邊找，小于就在左邊找，等于就表示找到了。這里的結果我使用的是返回數組的下標，如果沒有找到則返回-1。代碼如下：

1.遞歸法二分查找

//?遞歸二分查找
	public?static?int?binarySearch(Integer?array[],?int?key,?int?left,?int?right)?{
		int?center?=?left?+?(right?-?left)?/?2;?//?防止用(left+right)/2時left+high溢出
		if?(array[center]?==?key)?{
			System.out.println("找到了");
			return?center;
		}?else?if?(array[center]?<?key)?{
			return?binarySearch(array,?key,?center?+?1,?right);
		}?else?if?(array[center]?>?key)?{
			return?binarySearch(array,?key,?left,?center?-?1);
		}
		return?-1;
	}

2.非遞歸二分查找

//?非遞歸二分查找
	public?static?int?binarySearch1(Integer?array[],?int?key)?{
		int?left?=?0,?right?=?array.length-1;
		int?mid?=?-1;
		while?(left?>?1);
			if?(key?==?array[mid])?{
				return?mid;
			}?else?if?(key?<?array[mid])?{
				right?=?mid-1;
			}?else?{
				left?=?mid?+?1;
			}
		}
		return?-1;
	}

測試

	public?static?void?main(String[]?args)?{
		Integer?array[]?=?{?1,?2,?3,?4,?5,?6,?7,?8,?9,?10?};
//		System.out.println(binarySearch(array,?2,?0,?array.length));
		System.out.println(binarySearch1(array,?5));
	}

結果：4

表示找到了元素5，并在下標為4的地方。

附：C++代碼

int?binarySearch(vector&array,int?key){
????int?left?=?0,right?=?array.size()-1;
????int?mid?=?-1;
????while?(left?>?1);??//得到的是向下取整，如0,9的為4
????????cout<<mid<<endl;
????????if?(key?==?array[mid])?{
????????????return?mid;
????????}?else?if?(key?<?array[mid])?{
????????????right?=?mid-1;
????????}?else?{
????????????left?=?mid+1;
????????}
????}
????return?-1;
}