考虑到线性查找法的时间复杂度较高(O(n)), 我们可以选择使用二分查找算法.

二分查找算法只适用于有序数组(线性查找不需要满足该前提), 其时间复杂度为O(logn), 我们可以选择两种方式来完成二分查找算法.

要求 : 给定一个有序整形数组, 在该数组中, 找到目标值target, 如果找到, 则返回其在数组中的索引, 否则返回-1.

（1）方法1 ： 指针左闭右闭[i, j]----> 推导出循环条件 : i <= j

java">public static int BinarySearch_1(int[] arr, int target) {int i = 0;int j = arr.length - 1;//设置指针和初值while (i <= j) {int mid = i + (j - i) / 2;if (arr[mid] == target) {return mid;} else if (arr[mid] < target) {i = mid + 1;} else {j = mid - 1;}}return -1;}

方式2 ： 指针左闭右开[i, j) -----> 推导出循环条件 : i < j

java">public static int BinarySearch_2(int[] arr, int target) {int i = 0;int j = arr.length;while (i < j) {int mid = i + (j - i) / 2;if (arr[mid] > target) {j = mid;} else if (arr[mid] < target) {i = mid + 1;} else {return mid;}}return -1;}

test : 

java">@Testpublic void test1() {int[] arr = {1, 4, 6, 9, 11, 15, 57};int target = 9;int index1 = BinarySearch_1(arr, target);System.out.println("索引处是" + index1);int index2 = BinarySearch_2(arr, target);System.out.println("索引处是" + index2);}控制台 : 
索引处是3
索引处是3

而对于有重复性元素的数组来说, 查找值恰好为该重复的元素值, 上面两种方式返回的索引即为第一次被查找到的索引位置,.

test : 

java">@Testpublic void test1() {int[] arr = {9, 9, 9, 9, 9, 9};int target = 9;int index1 = BinarySearch_1(arr, target);System.out.println("索引处是" + index1);int index2 = BinarySearch_2(arr, target);System.out.println("索引处是" + index2);}控制台 : 
索引处是2
索引处是3

如果我们要求返回的索引是重复元素最左边的位置的索引, 即如上, 应返回索引0.我们应该对算法做出怎样的变化呢?

java">public static int BinarySearch_3(int[] arr, int target) {int i = 0;int j = arr.length - 1;//设置候选索引int cadicate = -1;int mid = i + (j - i) / 2;while (i <= j) {mid = i + (j - i) / 2;if (arr[mid] > target) {j = mid - 1;} else if (arr[mid] < target) {i = mid + 1;} else {//如果arr[mid] == target, 并不退出循环, 而是更新候选值, 继续向左排查cadicate = mid;j = mid - 1;}}return cadicate == -1 ? -1 : cadicate;}

test : 

java">@Testpublic void test1() {int[] arr = {1, 4, 7, 7, 7, 7,  8, 10};int target = 7;int index3 = BinarySearch_3(arr, target);System.out.println("索引处是" + index3);}控制台 : 
索引处是2

上述代码完成了返回了最左边的元素的索引, 如果我们想要得到最右边的元素的索引, 应该怎么办呢？非常简单, 只需要在else语句处略微改动.

java">else {//如果arr[mid] == target, 并不退出循环, 而是更新候选值, 继续向右排查cadicate = mid;i = mid + 1;
}

test : 

java">@Testpublic void test1() {int[] arr = {1, 4, 7, 7, 7, 7, 7, 8, 10};int target = 7;int index4 = BinarySearch_4(arr, target);System.out.println("索引处是" + index4);}控制台 : 
索引处是6