CSC 2200 Lecture Notes - Lecture 21: Binary Search Algorithm, Linear Search, Search Algorithm

• School: Wayne State University
• Department: Computer Science
• Course: CSC 2200
• Professor: Sushma Vallamkonda

Document Summary

Interpolation search finds a particular item by computing the probe position. Initially, the probe position is the position of the middle most item of the collection. If a match occurs, then the index of the item is returned: to split the list into two parts, we use the following method, mid=lo+((hi-lo)/(a[hi]-a[lo])))*(x-a[lo], a=list. Lo=lowest index of the list: hi=highest index of the list, a[n]= value stored at index n in the list. O(log n) of bst in favorable situations: algorithm. Step (cid:1005) start sear(cid:272)hi(cid:374)g data fro(cid:373) (cid:373)iddle of the list. Step (cid:1006) if it is a (cid:373)at(cid:272)h, retur(cid:374) the i(cid:374)dex of the ite(cid:373), a(cid:374)d exit. Step (cid:1007) if it is (cid:374)ot a (cid:373)at(cid:272)h, pro(cid:271)e positio(cid:374) Step (cid:1008) di(cid:448)ide the list usi(cid:374)g pro(cid:271)i(cid:374)g for(cid:373)ula a(cid:374)d fi(cid:374)d the (cid:374)e(cid:449) (cid:373)iddle. Step (cid:1009) if data is greater than middle, search in higher sub-list. Step (cid:1010) if data is s(cid:373)aller tha(cid:374) (cid:373)iddle, sear(cid:272)h i(cid:374) lo(cid:449)er su(cid:271)-list. Step (cid:1011) repeat u(cid:374)til (cid:373)at(cid:272)h: pseudocode.