【编程算法Ⅲ】查找某数、查找某个位置、局部最小值（二分法）（Python解法）

给你一个n代表有一个长度为n的有序数组，然后给你一个k，你需要判断这个k是否在数组里面，如果存在就返回这个数从左往右第一次出现位置的下标，如果不存在输出-1

二分法目标是找到序列的中点List[M]，与X进行比较，若相等则返回中点下标；否则，若List[M]>X，则在左边的子系列中查找X；若List[M]

①输入元素赋值，增加变量left、right，分别代表二分查找左端位置和右端位置；

②while循环直至left>right结束，mid中值位置，if中值等于aim目标值，输出mid，flag赋值0；if中值小于aim，说明aim应在中值右边，left赋值mid+1，对(mid+1,n-1)区间进行讨论;同理if中值大于aim，说明aim应在中值左边，right赋值mid-1，对(0,mid-1)区间进行讨论;

③若循环结束还未找到目标值，此时flag还是1，输出-1。

n,aim = map(int,input().split(' '))
lis = list(map(int,input().split(' ')))
left,right,flag= 0,n-1,-1
while left <= right:
    mid = (left+right)//2
    if lis[mid] == aim:
        flag = mid
        break
    elif lis[mid] < aim:
        left = mid + 1
    else:
        right = mid -1
print(flag)

你需要输入一个n，一个数k，然后输入一个长度为n个大小的数组arr，然后你需要在arr上找满足>=K的最左位置，并且输出这个位置，如果不存在这个位置就输出-1。

①输入元素赋值，增加变量left、right，分别代表二分查找左端位置和右端位置，增加变量flag；

②while循环同理，if中值大于等于目标值，right左移(移到中值位置左边)，直至right和left相等，此时flag处在大于等于aim的最左位置；

③若循环结束还未找到目标值，此时flag还是1，输出-1。

n,aim = map(int,input().split(' '))
lis = list(map(int,input().split(' ')))
left,right,flag= 0,n-1,-1
while left <= right:
    mid = (left+right)//2
    if lis[mid] == aim:
        flag = mid
        break
    elif lis[mid] < aim:
        left = mid + 1
    else:
        right = mid -1
print(flag)

定义局部最小的概念。arr长度为1时，arr[0]是局部最小。arr的长度为N(N>1)时，如果arr[0] < arr[1]，那么arr[0]是局部最小；如果arr[N-1]

主要分为三种情况：

①最左边两个值，如果0位置处的值小于1位置处，则0位置处为局部最小

②最右边的两个值，如果N-1位置处的值小于N-2位置处的值，则N-1处的值为局部最小值

③当0位置处的值大于1位置处的值，N-1的值大于N-2处的值，则中间某个位置或者某几个位置必然会有局部最小值

①输入元素赋值

②将前两种情况用代码形式表述出来

③讨论第三种情况，通过二分法查找局部最小值

④打印flag

n = int(input())
lis = list(map(int,input().split(' ')))
left,right,flag= 0,n-1,-1
if len(lis) == 1 or lis[0] < lis[1]:
    flag = 0
elif lis[n-2] > lis[n-1]:
    flag = n-1
else:
    while right >= left:
        mid = (left+right)//2
        if lis[mid] < lis[mid-1] and lis[mid] < lis[mid+1]:
            flag = mid
            break
        elif lis[mid] > lis[mid-1]:#如果成立，left-mid区间必存在局部最小值，mid-right区间可放弃
            right = mid
        elif lis[mid] > lis[mid+1]:#如果成立，mid-right区间必存在局部最小值，left-mid区间可放弃
            left = mid
print(flag)

大家如果有疑问都可以评论提出，有不足之处请大家批评指正，希望能多结识这方面的朋友，共同学习、共同进步。