https://github.com/dolphinmind/datastructure/tree/datastructure-array
主类
package com.github.dolphinmind.array.binarysearch;
/**
* @author dolphinmind
* @ClassName BinarySearch
* @description 704 二分法搜索
* 前提条件：有序数组，且无重复元素
* 循环判断：专注索引
* 逻辑判断：专注值
* 特殊情况：无结果，返回-1
* 技巧：mid = left + ((right - left) >> 1)
* @date 2024/7/31
*/
public class BinarySearch {
private int left;
private int right;
private int mid;
/**
* 二分法搜索：左闭右闭区间
* 分析：循环条件看索引，中间索引采用移位，逻辑判断条件优先选取目标，循环不成立有兜底 -1
*
* @param nums
* @param target
* @return
*/
public int binarySearchRightClose(int[] nums, int target) {
left = 0;
right = nums.length - 1;
while (left <= right) {
mid = left + ((right - left) >> 1);
if (target == nums[mid]) {
return mid;
} else if (target > nums[mid]) {
left = mid + 1;
} else if (target < nums[mid]) {
right = mid;
}
}
return -1;
}
/**
* 二分法搜索：左闭右开区间
* @param nums
* @param target
* @return
*/
public int binarySearchRightOpen(int[] nums, int target) {
left = 0;
right = nums.length;
while (left < right) {
mid = left + ((right - left) >> 1);
if (target == nums[mid]) {
return mid;
} else if (target > nums[mid]) {
left = mid + 1;
} else if (target < nums[mid]) {
right = mid - 1;
}
}
return -1;
}
}
测试类
package com.github.dolphinmind.array.binarusearch;
import com.github.dolphinmind.array.binarysearch.BinarySearch;
import org.junit.Test;
/**
* @author dolphinmind
* @ClassName ApiTest
* @description
* @date 2024/7/31
*/
public class BinarySearchTest {
/**
* 找房子编号，不要找房子里面的内容
*/
@Test
public void test_binarySearchRightClose() {
int[] nums = {-1, 0, 3, 5, 9, 12};
int target = 9;
BinarySearch binarySearch = new BinarySearch();
int result = binarySearch.binarySearchRightClose(nums, target);
System.out.println("左闭右闭区间选择：" + result);
}
@Test
public void test_binarySearchRightOpen() {
// int[] nums = {-1,0,3,5,9,12};
int[] nums = {};
int target = 2;
BinarySearch binarySearch = new BinarySearch();
int result = binarySearch.binarySearchRightOpen(nums, target);
System.out.println("左闭右开区间选择：" + result);
}
}