二分法的使用條件 二分法查找為什么只適用于順序存儲?
二分法查找為什么只適用于順序存儲?誰說它只能用于順序存儲,鏈式存儲也可以使用??匆幌露址ǖ乃惴枋觯渲刑岬剿荒苡糜陧樞虼鎯?。算法與其實現(xiàn)無關(guān)。我們只能說有些算法在某些方面更便于實現(xiàn)。二分法查找適
二分法查找為什么只適用于順序存儲?
誰說它只能用于順序存儲,鏈式存儲也可以使用。看一下二分法的算法描述,其中提到它只能用于順序存儲。
算法與其實現(xiàn)無關(guān)。我們只能說有些算法在某些方面更便于實現(xiàn)。
二分法查找適用于何種存儲方式的有序表?
二進制搜索是一種有效的搜索方法。在二進制搜索中,線性表的節(jié)點必須按鍵值排序,線性表按順序存儲。二進制搜索的優(yōu)點是比較次數(shù)少,搜索速度快,平均搜索長度小。經(jīng)過{loge n次比較,搜索過程就可以完成了。同時,有序表的插入和刪除需要平均比較和移動表中一半的元素。一般來說,二進制搜索適用于相對固定的數(shù)據(jù),二進制搜索只適用于線性表的順序存儲。
下列數(shù)據(jù)結(jié)構(gòu)中,能用二分法進行查找的是( )?
A.按順序存儲的有序線性列表的二分法僅適用于有序列表。其次,由于鏈表對節(jié)點的操作只能以P->next的方式進行,不適合下標操作,因此不能使用D.有序線性表。但是,可以使用有序線性列表
適用的前提條件:
1。存儲在數(shù)組中(如一維數(shù)組)
2數(shù)組元素按順序(如升序)搜索的基本思想:半搜索,將要搜索的元素設(shè)為值,將值與中間元素(中間=左(右-左)/2比較,這樣做的好處是防止中間元素越界)。如果小于中間值,搜索范圍將繼續(xù)在中間1,如果大于中間值,搜索范圍將在中間1-1。如果它等于中間值,則搜索的結(jié)束索引元素為value=middle。