基于C语言实现的二分法

68 阅读 0 评论 45 点赞

我是靠谱客的博主活力云朵，这篇文章主要介绍基于C语言实现的二分法，现在分享给大家，希望可以做个参考。

二分法适用于一个已经排好序的，不管是升序还是降序的有序数组。二分查找法：给定一个目标数字，去到这个有序的数组，查找是否存在这个数，如果存在这个数就返回对应的数字下标，如果不存在就返回-1.
left=0;
right=length-1;
mid=(left+right)/2

left从左往右遍历，如果遍历得到的mid值还是小于给定目标对应的数字就+1，即继续往右遍历
right从右往左遍历，如果遍历得到的mid值还是大于给定目标对应的数字就-1，即继续往左遍历
如果mid对应的数字刚好等于给定的目标数字就返回mid

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int search(int* nums, int numsSize, int target){
    int left = 0;
    int right = numsSize-1;
    int mid = 0;
    //若left小于等于right，说明区间中元素不为0
    while(left<=right) {
        //更新查找下标mid的值
        middle = (left+right)/2;
        //此时target可能会在[left,mid-1]区间中
        if(nums[mid] > target) {
            right = mid-1;
        } 
        //此时target可能会在[mid+1,right]区间中
        else if(nums[mid] < target) {
            left = mid+1;
        } 
        //当前下标元素等于target值时，返回mid
        else if(nums[middle] == target){
            return mid;
        }
    }
    //若未找到target元素，返回-1
    return -1;}