在数组中找到一个局部最小的位置

#include<iostream>
(720)#include<algorithm>

using namespace std;

int main(){
    int n;
    cin>>n;
    if(n == 1 ){
        cout<<0<<endl;
        return 0;
    }
    int inp[n];
    for(int i = 0; i < n; i++){
        scanf("%d",&inp[i]);
    }
    if(inp[0] < inp[1]){
        cout<<0<<endl;
        return 0;
    }
    else if(inp[n - 1] < inp[n - 2]){
        cout<<n - 1<<endl;
        return 0;
    }
    int left = 1, right = n - 2;
    while(left < right){
        int mid = (left + right) / 2;
        if(inp[mid] > inp[mid - 1]){
            right  = mid - 1;
        }
        else if(inp[mid] > inp[mid + 1]){
            left = mid + 1;
        }
        else{
            cout<<mid<<endl;
            return 0;
        }
    }
    cout<<left<<endl;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
//求波谷
int findMixNum(vector<int>& arr) {
    if (arr.size()< 2) return 0;
    int l = 0, r = arr.size() - 1;
    while (l < r) {
        int mid = (r - l) / 2 + l;
        if (arr[mid] < arr[mid + 1]) {
            r = mid;
        }
        else {
            l = mid + 1;
        }
    }
    return l;
}
int main() {
    int n;
    cin >> n;
    vector<int> arr(n, 0);
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }
    cout << findMixNum(arr);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
//求波谷
int findMixNum(vector<int>& arr) {
    if (arr.size()< 2) return 0;
    int l = 0, r = arr.size() - 1;
    while (l < r) {
        int mid = (r + l + 1) / 2;
        if (arr[mid] < arr[mid - 1]) {
            l = mid;
        }
        else {
            r = mid - 1;
        }
    }
    return l;
}
int main() {
    int n;
    cin >> n;
    vector<int> arr(n, 0);
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }
    cout << findMixNum(arr);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin>>n;
    int a[n], l=0, r=n-1;
    for(int i=0;i<n;i++)
        cin>>a[i];
    if(n==1)
        cout<<0<<endl;
    else{
        if(a[n-1]<a[n-2])
            cout<<n-1<<endl;
        else if(a[0]<a[1])
            cout<<0<<endl;
        else{
            while(l<=r){
                int m = (l+r)>>1;
                if(a[m]<a[m-1] && a[m]<a[m+1]){
                    cout<<m<<endl;
                    break;
                }else if(a[m]>a[m-1])
                    r = m-1;
                else
                    l = m+1;
            }
        }
    }
    return 0;
}

int main(){

    // freopen("input.txt","r",stdin); 
    int n;
    scanf("%d", &n);
    int arr[n];
    for(int i = 0; i < n; i++){
        scanf("%d", &arr[i]);
    }
    if(n == 1){
        cout << 0 << endl;
        return 0;
    } else {
        if(arr[n-1] < arr[n-2]){
            cout << n-1 <<endl;
            return 0;
        } 
        if(arr[0] < arr[1]){
            cout << 0 << endl;
        }
    }

    int l = 0, r = n-1;
    while(l <= r){
        int mid = int((l + r) / 2);
        if(arr[mid-1] > arr[mid] && arr[mid+1] > arr[mid]){
            cout << mid << endl;
            return 0;
        } else if(arr[mid-1] < arr[mid]){
            r = mid-1;
        } else {
            l = mid+1;
        }
    }

    return EXIT_SUCCESS;
}
往负梯度的方向进行二分查找

import java.util.*;
public class Main {
    public static void main(String[]args){
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int[] arr = new int[N];
        for(int i =0; i < N;i++) {
            arr[i] = scan.nextInt();
        }
        System.out.println(partialMinPos(arr));
    }
    public static int partialMinPos(int[] arr) {
        if (arr == null || arr.length == 0) return -1;
        if (arr.length == 1 || arr[0] < arr[1]) return 0;
        if (arr[arr.length - 1] < arr[arr.length - 2]) return arr.length - 1;

        int l = 0;
        int r = arr.length - 1;

        while (l + 1 < r) {
            int mid = (l + r) / 2;
            if (arr[mid] > arr[mid - 1]) {
                r = mid;
            } else if (arr[mid] > arr[mid + 1]) {
                l = mid;
            } else {
                return mid;
            }
        }
        return -1;
    }
}

import java.io.*;
public class Main{
    public static void main(String[]args) throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n= Integer.valueOf(bf.readLine());
        String[] str = bf.readLine().split(" ");
        int[] arr = new int[n];
        for(int i=0; i<n; i++){
            arr[i] = Integer.valueOf(str[i]);
        }
        bf.close();
        
        int s = 0, e = n-1, m;
        while(s<e){
            m = (s+e)>>1;
            if(arr[m+1] < arr[m]){
                s = m+1;
            }else{
                e = m;
            }
        }
        System.out.println(s);
    }
}

#include "stdio.h"
#include "stdlib.h"
#include "string.h"


int main()
{
    int arr[100861] = {0};
    int n, i, tmp = 0;

    scanf("%d", &n);
    for (i = 0; i < n; i++)
    {
        scanf("%d", &arr[i]);
        if ((i > 1) && (tmp == 0)) //如果0<i<n-1且还没找到局部最小
        {
            if ((arr[i - 1] < arr[i - 1 - 1]) && (arr[i - 1] < arr[i - 1 + 1]))
            {
                tmp = i - 1; //找到了局部最小
            }
        }
    }
    if ((n == 1) || (arr[0] < arr[1])) //arr的长度为1或arr[0]<arr[1]时局部最小是0
        printf("0\n");
    else if (arr[n - 1] < arr[n - 2]) //看看n-1是不是局部最小
        printf("%d\n", n - 1);
    else //如果0<i<n就输出上面找到的局部最小
        printf("%d\n", tmp);
    return 0;
}