1. 循环法
public static int binarySearch(int[] arr, int low, int high, int target) {
while (low <= high) {
// 这样写主要是避免溢出的情况,以及>>优先级小于+,避免出现死循环
int mid = low + ((high - low) >> 1);
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
2. 递归
public static int binarySearch1(int[] array, int low, int high, int target) {
if (low < high) {
int mid = low + ((high - low) >> 1);
if (array[mid] == target) {
return mid;
} else if (array[mid] > target) {
return binarySearch(array, low, mid - 1, target);
} else {
return binarySearch(array, mid + 1, high, target);
}
}
return -1;
}
3. 元素中有重复的二分查找
假设现在有个数组里面有重复元素,并且按照增序排列,如果有相同元素,返回最左侧的第一个重复元素的位置。文章来源:https://www.toymoban.com/news/detail-643569.html
核心思路也是比较简单了,当找到第一个重复的元素时候,记录位置,然后向左移动,左边的不是目标元素,就意味着左边没有重复的目标元素,然后+1就是目标元素的位置文章来源地址https://www.toymoban.com/news/detail-643569.html
public static int search(int[] nums, int target) {
if (nums == null || nums.length == 0)
return -1;
int low = 0;
int high = nums.length - 1;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (nums[mid] < target) {
low = mid + 1;
} else if (nums[mid] > target) {
high = mid - 1;
} else {
// 找到了符合目标元素的数据位置,然后一直往左遍历,知道不是目标元素或者索引为0的时候停止
while (mid != 0 && nums[mid] == target) {
mid--;
}
if (mid == 0 && nums[mid] == target) {
return mid;
}
return mid + 1;
}
}
return -1;
}
到了这里,关于算法通关村——透彻理解二分查找的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!