# 1. 傳統二分查找
假設一個數組有序，且元素僅出現一次，那么二分查找為：
~~~
/**
* 二分查找
* @param arr 待查找數組
* @param target 目標值
* @return 下標
*/
public int binarySearch(int[] arr, int target){
if(arr == null || arr.length == 0) return -1;
int left = 0, right = arr.length - 1;
while(left < right) {
int mid = (left + right) / 2;
if(arr[mid] > target) right = mid - 1;
else if(arr[mid] < target) left = mid + 1;
else return mid;
}
return arr[left] == target ? left : -1;
}
~~~
# 2. 二分查找返回最左邊元素
即數組有序，但是數組中元素不止出現一次，如果出現多次就返回重復的這個元素的首次出現的位置。可以在上面的代碼基礎上做一個簡單的修改：
~~~
/**
* 數組中元素不止出現一次，如果出現多次就返回重復的這個元素的首次出現的位置。
* @param arr 待查找數組
* @param target 目標值
* @return 下標
*/
public int binarySearch(int[] arr, int target) {
if (arr == null || arr.length == 0) return -1;
int left = 0, right = arr.length - 1;
while (left < right) {
int mid = (left + right) / 2;
if (arr[mid] > target) right = mid - 1; // 目標值在左邊
else if (arr[mid] < target) left = mid + 1; // 目標值在右邊
else { // 找到目標值
// 找最左邊元素
int i = mid;
for (; i > 0; i--) {
if (arr[mid] != arr[i]) break;
}
return i + 1;
}
}
return arr[left] == target ? left : -1;
}
~~~
當然上面的代碼雖然理解邏輯比較容易易懂，但是這個代碼卻略顯復雜，且不怎么美觀，可以參考下面的代碼：
~~~
/**
* 數組中元素不止出現一次，如果出現多次就返回重復的這個元素的首次出現的位置。
* @param arr 待查找數組
* @param target 目標值
* @return 下標
*/
public int binarySearch(int[] arr, int target){
if(arr == null || arr.length == 0) return -1;
int left = 0, right = arr.length - 1;
int ans = -1; // 記錄下標，從右到左移動
while(left < right) {
int mid = (left + right) / 2;
if(arr[mid] >= target) { // 等于默認也就是不滿足，需要再次二分查找
right = mid - 1;
ans = right;
}
else left = mid + 1;
}
return ans;
}
~~~
