考虑到线性查找法的时间复杂度较高(O(n)), 我们可以选择使用二分查找算法.
二分查找算法只适用于有序数组(线性查找不需要满足该前提), 其时间复杂度为O(logn), 我们可以选择两种方式来完成二分查找算法.
要求 : 给定一个有序整形数组, 在该数组中, 找到目标值target, 如果找到, 则返回其在数组中的索引, 否则返回-1.
（1）方法1 ： 指针左闭右闭[i, j]----> 推导出循环条件 : i <= j
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
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 :
@Test public 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 :
@Test public 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.我们应该对算法做出怎样的变化呢?
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 :
@Test public 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语句处略微改动.
else { //如果arr[mid] == target, 并不退出循环, 而是更新候选值, 继续向右排查 cadicate = mid; i = mid + 1; }
test :
@Test public 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
