給定一個(gè)有序的整數(shù)數(shù)列步藕,可以有負(fù)數(shù),可以有重復(fù)挑格,找出a[i]=i的數(shù)并返回漱抓,如果沒有返回-1.(百度二面)
分析:
傳統(tǒng)二分法失效,考慮數(shù)列 -1恕齐, 0乞娄, 1, 2显歧, 4仪或, 6, 7士骤, 8
以及數(shù)列 1范删, 2, 3拷肌, 4到旦, 4, 4巨缘, 5添忘, 6
無(wú)法判斷具體我們要找的是在左邊還是右邊。a[mid] < mid or a[mid] > mid
故考慮使用遞歸二分查找mid左右的數(shù)組若锁。