# 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;
}
~~~
