盡可能使用二分查找
? ?假設在 left ?right 之間查找 ?
? ? 關鍵是mid處理過程 導致 left 跟 right 的改變 ?控制去哪里尋找
? ? 分如下情況：
? ?若 mid處 不為空，并且 此處就是 str ? 那么記下 mid ?，同時把right-1 ? （往左尋找）
? ?若 mid處不為空，并且此處不是str，比較字典順序
? ?若 mid處為空， 則通過while控制向左邊移動，左邊沒有元素，或者找到的字典順序小于str，left=mid+1
? ? ? ? ? ? ? ? ? ? ? ? ? ?字典順序大于str ?或者等于 str ?此時 res = strs[i].equals(str) ? i : res ? ? ? ?然后right=i-1; ?注意是i-1 ?此處的位置-1
package TT;import java.awt.List;public class Test3 {public static int getIndex (String[] strs, String str){if(strs==null || strs.length==0 ||str ==null){return -1;}int res = -1;int left =0;int right = strs.length;int mid = 0;int i =0;while(left <= right){mid=(left+right)/2;if(strs[mid]!=null && strs[mid].equals(str)){res = mid;right = mid-1;}else if(strs[mid]!=null){if(strs[mid].compareTo(str)<0){left = mid+1;}else {right = mid-1;}}else{i = mid; //把此時的mid記下了while(strs[i]==null && --i>=left);if(i<left || strs[i].compareTo(str)<0){left = mid+1;}else{res =strs[i].equals(str) ? i :res;right = i-1;}}}return res;}public static void main(String[] args){String[] objects = new String[6];objects[0]=null;objects[1]="b";objects[2]=null;objects[3]="b";objects[4]=null;objects[5]="a";String s = "b";int a = getIndex(objects,s);System.out.println(a);} }
