title: 查找
date: 2022-08-18 14:59:55
tags:
- 数据结构
categories:
- 408
- 数据结构
- 代码

看到有序数组首先想能不能折半查找

折半查找

#include <iostream>
#include <vector>
using namespace std;

/**
 * @description: 
 * @param {int} target 目标函数
 * @param {int} arr 数组
 * @param {int} len 长度
 * @return {*} 找到 返回mid，未找到返回-1
 */
int binary_search(int target, int arr[], int len){
    int l = 0, r = len - 1, mid;
    while (l < r)
    {
        mid = l + (r - l)/2; //防止int溢出
        if(arr[mid] < target)
            l = mid + 1;
        else if(target < arr[mid])
            r = mid -1;
        else
            return mid;
    }
    // return l; // 返回插入位置
    return -1;
    
}


//第二种写法
int binary_search(int target, int arr[], int len){
    int l = 0, r = len - 1, mid;
    while (l < r)
    {
        mid = l + (r - l)/2; //防止int溢出
        if(arr[mid] == target)
            return mid;
        else if(target < arr[mid])
            r = mid - 1;
        else
            l = mid + 1;
            
    }
    return -1;
    
}

int main(int argc, char const *argv[])
{
    int arr[] = {1, 2, 4, 6, 7, 10, 11, 19, 24, 30};
    int target = 4;
    int len = sizeof(arr)/sizeof(int) - 1;
    printf("target: %d, pos: %d\n", target, binary_search(target, arr, len));
    return 0;
}