current position:Home>C language algorithm problem: binary search

C language algorithm problem: binary search

2022-01-27 02:37:45 WE-ubytt

subject :

Given a n The elements are ordered ( Ascending ) integer array nums And a target value target , Write a function search nums Medium
target, If the target value has a return subscript , Otherwise return to -1.

Example 1:

Input : nums = [-1,0,3,5,9,12], target = 9
Output : 4
explain : 9 Appear in the nums And the subscript is 4

Example 2:

Input : nums = [-1,0,3,5,9,12], target = 2
Output : -1
explain : 2 non-existent nums So back to -1

Tips :

1. You can assume nums All elements in are not repeated .
2. n Will be in [1, 10000] Between .
3. nums Each element of will be in [-9999,9999] Between .

source : Power button (LeetCode)
link :https://leetcode-cn.com/problems/binary-search
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Ideas :
For binary search , The data must be orderly , Let's assume that the data is in ascending order , Divide the data into two parts , The left endpoint is left, The right endpoint is right, Midpoint is mid.
By comparing the number you want to find target And num[mid] Size :
If target < nums[mid] explain target stay [left,mid] Between ;
If target > nums[mid] explain target stay [mid,right] Between .
By repeating the above operations, we can find what we want to find target The subscript of .

Complexity analysis :

Time complexity :O(log n), among n Is the length of the array .
Spatial complexity :O(1).

Code :

int search(int* nums, int numsSize, int target)
{
    
    int left = 0;
    int right = numsSize - 1;

    //  Condition of circulation : When the left subscript is greater than the right subscript , The cycle stops 
    while(left <= right)
    {
    
        int mid = (left + right) / 2;
        //  The number to be found is to the left of the midpoint 
        if(target < nums[mid])
        {
    
            right = mid - 1;
        }
        //  The number to be found is to the right of the midpoint 
        else if(target > nums[mid])
        {
    
            left = mid + 1;
        }
        //  eureka 
        else
        {
    
            return mid;
        }
    }
    //  Did not find 
    return -1;
}

copyright notice
author[WE-ubytt],Please bring the original link to reprint, thank you.
https://en.cdmana.com/2022/01/202201270237435920.html

Random recommended