Shulou(Shulou.com)05/31 Report--

This article mainly explains "how to use the C language binary search method". The explanation content in this article is simple and clear, easy to learn and understand. Please follow the ideas of Xiaobian to study and learn "how to use the C language binary search method" together.

Example 1:

Input: nums = [-1,0,3,5,9,12], target = 9

output: 4

Explanation: 9 appears in nums and subscripts 4

Example 2:

Input: nums = [-1,0,3,5,9,12], target = 2

Output: -1

Explanation: 2 does not exist in nums so returns-1

Tip:

You can assume that all elements in nums are not repeated.

n will be between [1, 10000].

Each element of nums will be between [-9999, 9999].

Note that the array is an ordered array, and there are no duplicate elements in the array, because once there are duplicate elements, the subscript of the elements returned by the binary search method may not be unique.

In the process of binary search, keep the invariant, that is, in the while search, each boundary processing must adhere to the definition of the interval to operate, this is the loop invariant rule.

There are two kinds of definitions of dichotomy: left closed right closed (left, right), or left closed right open (left, right).

Dichotomy, first way.

In the first case, we define target as being in an interval closed on the left and closed on the right, i.e.[left, right]. Since target is defined in the [left, right] interval, there are two points as follows:

while (left 1); if (nums[middle] > target) { right = middle; // target in left interval, in [left, middle) } else if (nums[middle] < target) { left = middle + 1; // target in the right interval, in [middle + 1, right) } else { // nums[middle] == target return middle; //Find the target value in the array, return the subscript directly } } //Target not found return -1; }};

In the above two ways, pay attention to their differences:

The initial value of right is different.

② Difference between update values of left and right sections

Thank you for reading, the above is "C language binary search method how to use" the content, after the study of this article, I believe we have a deeper understanding of how to use the C language binary search method, the specific use of the situation also needs to be verified by practice. Here is, Xiaobian will push more articles related to knowledge points for everyone, welcome to pay attention!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.