C语言基础练习题--二分查找

旧城等待， 2022-12-25 12:56 175阅读 0赞

## 题目 ##

在排序数组中查找元素的第一个和最后一个位置  
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 \[-1, -1\]。

示例 1：

输入：nums = \[5,7,7,8,8,10\], target = 8  
输出：\[3,4\]  
示例 2：

输入：nums = \[5,7,7,8,8,10\], target = 6  
输出：\[-1,-1\]  
示例 3：

输入：nums = \[\], target = 0  
输出：\[-1,-1\]

开始看到这道题，大师匈就在想用遍历数组的方法去查找，但是凡事碰到这种查找类型的题目，应该要想到二分查找去做。

int search(int* nums,int numsSize,int target,bool left_or_right)
    { 
        int start = 0,end = numsSize-1;
        int mid = 0,result = numsSize;
        while(start <= end)
        { 
            mid = (start + end)/2;
            if(nums[mid] > target ||(left_or_right && nums[mid] >= target))
            { 
                end = mid -1;
                result = mid;
            }
            else
            { 
                start = mid + 1;
            }
        }
        return result;
    }
    int* searchRange(int* nums, int numsSize, int target, int* returnSize){ 
        int left = search(nums,numsSize,target,1);
        int right = search(nums,numsSize,target,0) - 1;
        int* result = malloc(sizeof(int)*2);
        *returnSize = 2;
        if(left<=right && nums[left]==target && nums[right]==target )
        { 
            result[0] = left;
            result[1] = right;
            return result;
        }
        result[0] = -1;
        result[1] = -1;
        return result;
    }

在这里有一个比较巧的是对标志位left\_or\_right的使用，看似简单，但这确实一个很好的技巧，很多人包括大师匈经常会直接暴力的使用条件语句，使得产生了更多的代码，这里应该记下来这种程序小技巧。

题目比较简单，大师匈不在多说了，但是这种看似简单的基础题，却能锻炼扎实的基础，一起进步，共勉。