# 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）

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;
}
``````