代码随想录突击版学习

First Post:

Last Update:

二分查找

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

示例 1:

1
2
3
输入: nums = [-1,0,3,5,9,12], target = 9     
输出: 4       
解释: 9 出现在 nums 中并且下标为 4

示例 2:

1
2
3
输入: nums = [-1,0,3,5,9,12], target = 2     
输出: -1        
解释: 2 不存在 nums 中因此返回 -1

提示：

  • 你可以假设 nums 中的所有元素是不重复的。
  • n 将在 [1, 10000]之间。
  • nums 的每个元素都将在 [-9999, 9999]之间。

思路

首先，二分查找的使用限制：

​ 二分查找只使用于有序数组中，二分查找的边界需要进行判断

使用python编写的模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#在单调递增序列a中查找>=x的数中最小的一个（即x或x的后继）
def findMin(a,x,low,high):
    while low<high:
        mid=int((low+high)/2)
        if(a[mid]>=x):
            high=mid
        else:
            low=mid+1
    print(a[high])
#在单调递增序列a中查找<=x的数中最大的一个（即x或x的前驱）
def findMax(a,x,low,high):
    while low<high:
        mid=int((low+high+1)/2)
        if(a[mid]<=x):
            low=mid
        else:
            high = mid-1
    print(a[low])
a=[1,2,3,4,5,6,7,8,9,10]
x=3
low=0
high=len(a)-1
findMin(a,x,low,high)
findMax(a,x,low,high)

那么，使用java怎么实现呢？

≡