查找
一田弥、例2.9 找x
此題很簡單 線性遍歷數(shù)組查找 O(m) 只是為了回憶該題型?
發(fā)現(xiàn)自己寫的和參考實例不同的地方：我寫了一個flag判斷是否找到宝踪，并且找到就直接輸出；參考實例則直接把ans設(shè)置為-1联四，找到也把下標(biāo)賦值給ans境蜕，最后統(tǒng)一輸出。（邏輯挺不一樣的 不過都不影響）
二汽馋、例2.10 查找學(xué)生信息
首先回歸了一下二分法的思路 注意該方法的基礎(chǔ)是待查找數(shù)列已經(jīng)排好序了侮东；當(dāng)出現(xiàn)查找起始點大于查找結(jié)束點時，說明查找子集已經(jīng)為空集豹芯，查找失敗悄雅。該法的時間復(fù)雜度為O(logm)
此題如果用線性查找，復(fù)雜度會達到O(n*m)千萬數(shù)量級铁蹈，而利用二分查找可以優(yōu)化到O(nlogn*nlogm) 其中nlogn為升序排列復(fù)雜度
遇到的問題：
1） 忘記要升序排序了宽闲； 后來排序還是用的cmp 忘了可以重載<就不要cmp了； 而且cmp中比較字符串大小不確定如何實現(xiàn)握牧，第一遍是return !strcmp(); 第二遍改為return strcmp()>0對了
2）結(jié)合數(shù)組和結(jié)構(gòu)后二分查找代碼實現(xiàn)部分下標(biāo)比較混亂 容易想不清楚 base/i和top/j和(base+top)/2或(i+j)/2
3）初始化的問題 對大數(shù)組在外部定義 內(nèi)部初始化時 直接初始化為{}好像不行 必須for循環(huán)來一步步{} （好吧這個還待確認?
和示例的區(qū)別：
1）示例的輸出都是 輸入一行就輸出一行結(jié)果 我的處理是輸入所有的待查序號后 再統(tǒng)一輸出結(jié)果 這個需要在確認一下?
2）示例沒有直接找到就輸出 而是記住目標(biāo)元素的下標(biāo) 賦值給ans 而ans初始化為-1 所以可以最后直接判斷是否=-1來判斷是否找到 再統(tǒng)一輸出 同例1
擴展：
二分查找的定界應(yīng)用：如：在一個升序數(shù)組中容诬，確定一個下標(biāo)點，使在這個下標(biāo)點之前的數(shù)字均小于等于目標(biāo)數(shù)字沿腰，而數(shù)組中的剩余部分均大于目標(biāo)數(shù)字放案。
編寫程序：上例二分查找中的while循環(huán)條件里的跳出循環(huán)的top 即為該問題的數(shù)組下標(biāo)點。?
