力扣704(java&python)-二分查找（简单）

标签：right java target nums 704 mid 力扣 int left

题目：

给定一个 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]之间。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/binary-search
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：

这就是一个标准的二分查找题呀！这是一个有序的数组，设置左右指针并初始化：left = 0, right = nums.length - 1，计算mid = 

= left + (right - left + 1) / 2 （向上取整），循环条件是：left < right：

• nums[mid] <= target ： 说明此时mid对应的值可能为结果以及它右边的数可能为结果，即搜索区间就会变为[mid, right]，即 left = mid（避免只有两个数的时候，mid = left + (right - left ) / 2向下取整时 mid == left，出现只能在[mid, right]中死循环，不能缩小搜索区间，故mid才变为向上取整 ）；
• nums[mid] > target：说明在mid右边的数都大于target,因此搜索区间应该变为[left, mid - 1]，即 right = mid - 1；

退出循环时left == right， 此时搜索区间缩小为一个点，这时left或者right就可能为答案，就需要对 nums[left] 与 target 进行比较，如果两者相等返回left，不相等说明最终没找到，返回 -1。

java代码：

 1 class Solution {
 2     public int search(int[] nums, int target) {
 3         int left = 0, right = nums.length - 1;
 4         while (left < right){
 5             int mid = left + (right - left + 1) / 2;
 6             if (nums[mid] <= target){
 7                 //搜索区间为：[mid, right]
 8                 left = mid;
 9             }else{
10                 //搜索区间为：[left, mid-1]
11                 right = mid - 1;
12             }
13         }
14         return nums[left] == target ? left : -1;
15     }
16 }

 python3代码:

 1 class Solution:
 2     def search(self, nums: List[int], target: int) -> int:
 3         left, right = 0, len(nums) - 1
 4         while left < right:
 5             mid = left + (right - left + 1) // 2
 6             if nums[mid] <= target:
 7                 left = mid
 8             else:
 9                  right = mid - 1
10         return  right if nums[right] == target else -1

 另一种写法：

java代码：

 1 class Solution {
 2     public int search(int[] nums, int target) {
 3         int left = 0, right = nums.length - 1;
 4         while (left <= right){
 5             int mid = left + (right - left) / 2;
 6             if (nums[mid] < target){
 7                 //搜索区间为：[mid+1, right]
 8                 left = mid + 1;
 9             }else if (nums[mid] > target){
10                 //搜索区间为：[left, mid-1]
11                 right = mid - 1;
12             }else{
13                 return mid;
14             }
15         }
16         return -1;
17     }
18 }

 小知识：

python中的三目运算：

标签：right,java,target,nums,704,mid,力扣,int,left
From： https://www.cnblogs.com/liu-myu/p/16902175.html