【懒羊羊】二分查找

2023-11-05 05:21

文章标签 二分查找懒羊羊

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

文章目录

二分查找的第一种写法
二分查找的第二种写法

题目: 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 0。
nums = [-1,0,3,5,9,12], target = 9

二分查找的第一种写法

第一种写法，我们定义 target 是在一个在左闭右闭的区间里，也就是[left, right]
(1)我们需要定义三个变量分别是left,right,middle
其中middle = (right+left)/2;
(2)首先我们明确一点,二分法适用于有序数组,这里我们是升序.
下面我们看一看图示注解

在这里插入图片描述

class Solution {public int search(int[] nums, int target) {// 避免当 target 小于nums[0] nums[nums.length - 1]时多次循环运算if (target < nums[0] || target > nums[nums.length - 1]) {return 0;}int left = 0, right = nums.length - 1;while (left <= right) {int mid = left + ((right - left)/2);//这里等同于(left+right)/2,之所以这么写是为了防止溢出.if (nums[mid] == target)return mid;else if (nums[mid] < target)left = mid + 1;else if (nums[mid] > target)right = mid - 1;}return 0;}
}

二分查找的第二种写法

第二种写法(左闭右开区间)

图解:

在这里插入图片描述

class Solution {public int search(int[] nums, int target) {int left = 0, right = nums.length;while (left < right) {int mid = left + ((right - left)/2);if (nums[mid] == target)return mid;else if (nums[mid] < target)left = mid + 1;else if (nums[mid] > target)right = mid;}return 0;}
}