【数组】-Lc704-二分查找（左闭右闭、左闭右开）

本文主要是介绍【数组】-Lc704-二分查找（左闭右闭、左闭右开），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

写在前面

最近想复习一下数据结构与算法相关的内容，找一些题来做一做。如有更好思路，欢迎指正。

一、场景描述

给定一个n个元素有序的（升序）整型数组nums和一个目标值target，写一个函数搜索nums中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4示例2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1提示：
你可以假设 nums中的所有元素是不重复的。
n将在[1, 10000]之间。
nums的每个元素都将在[-9999, 9999]之间

二、具体步骤

1.环境说明

名称	说明
IntelliJ IDEA	2019.2

2.代码

以下为Java版本实现：

public class Lc704_binarySearch {public static void main(String[] args) {int[] nums = {1, 2, 4, 5, 8};System.out.println(binarySearch(nums, 4));System.out.println(binarySearch(nums, 3));//        3 = 11 >> 1 = 1
//        9 = 1001 >> 1 = 4
//        System.out.println( 3 * 3 >> 1);    // 4，乘法的优先级高于移位运算符//        101 = 5 >> 2
//        System.out.println( 3 + 2 >> 1);    // 2, 加法的优先级高于移位运算符}/*** 二分查找* num特性，左闭右闭[low, high]* 左闭右闭[low, high] 即 low = 0,  high = nums.length - 1** 时间复杂度 O（logn）** 思路：* 返回值是int** 定义low=0, high=nums.length-1** while(low<=high)* int mid = low + (high - low) / 2** 判断target于nums[mid]关系* target < nums[mid]，high = mid - 1* target > nums[mid], low = mid + 1* 否则，返回mid** 循环结束，没找到，返回-1** 最后，加上边界判断（比最小值还小，比最大值还大，即不存在）** @param nums   元素有序不重复的* @param target 目标值* @return*/public static int binarySearch(int[] nums, int target) {if (target < nums[0] || target > nums[nums.length - 1]) {return -1;}int low = 0, high = nums.length - 1;// 1、注意边界, low = high 有效while (low <= high) {// 2、防止low + high超出int范围，造成溢出
//            int mid = (low + high) >> 1;// 3、移位运算的优先级要低于加减，所以要多加一个括号
//            int mid = low + (high - low) >> 1;int mid = low + ((high - low) >> 1);if (target < nums[mid]) {high = mid - 1;} else if (target > nums[mid]) {low = mid + 1;} else {return mid;}}return -1;}/*** 二分查找* num特性，左闭右开[low, high)* 左闭右开[low, high) 即 low = 0,  high = nums.length** @param nums   元素有序不重复的* @param target 目标值* @return*/public static int binarySearch0(int[] nums, int target) {if (target < nums[0] || target > nums[nums.length - 1]) {return -1;}int low = 0, high = nums.length;// 1、注意边界, low = high无意义的while (low < high) {int mid = low + ((high - low) >> 1);if (target < nums[mid]) {// 2、保持右开，target 在左区间，在[low, mid)high = mid;} else if (target > nums[mid]) {low = mid + 1;} else {return mid;}}return -1;}}