考虑到线性查找法的时间复杂度较高(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
