LeetCode[33] 搜索旋转排序数组（二分查找）

Love The Way You Lie 2022-12-18 01:56 136阅读 0赞

> 前言：今天是1024程序员节，祝各位道友身体健康，工作顺利！1024当然离不开写程序啦，哈哈~ 在此分享一道二分查找算法的 LeetCode题目 [33. 搜索旋转排序数组][33.]

## 题目描述 ##

给你一个升序排列的整数数组 nums ，和一个整数 target 。  
假设按照升序排序的数组在预先未知的某个点上进行了旋转。（例如，数组 \[0,1,2,4,5,6,7\] 可能变为 \[4,5,6,7,0,1,2\] ）。  
请你在数组中搜索 target ，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

示例 1：

> 输入：nums = \[4,5,6,7,0,1,2\], target = 0  
> 输出：4

示例 2：

> 输入：nums = \[4,5,6,7,0,1,2\], target = 3  
> 输出：-1

示例 3：

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

提示：

> 1 <= nums.length <= 5000  
> \-10^4 <= nums\[i\] <= 10^4  
> nums 中的每个值都 独一无二  
> nums 肯定会在某个点上旋转  
> \-10^4 <= target <= 10^4

## 算法思路 ##

利用典型的二分思想查找目标，分以下情况讨论：

1.  当每一次二分后，总有一半是升序的，因此需要判断左右哪段为升序；
2.  如果左半部分为升序，就判断 target 位置是否在 0 ~ mid 之间，若存在，则查找区间缩小到左区间，否则缩小到右区间，继续二分查找
3.  如果右半部分为升序，就判断 target 位置是否在 mid ~ numsSize - 1 之间，若存在，则查找区间缩小到右区间，否则缩小到左区间，继续二分查找
4.  结束二分条件：直到找到目标target，或者区间 < 0

## 代码实现 ##

int search(int* nums, int numsSize, int target){
        
        int left = 0;
        int right = numsSize - 1;
        int mid = 0;
        
        while(left <= right) {
        
            mid = (left + right) / 2;
            if(nums[mid] == target) {
        
                return mid;
            }
            // 当左半部分为升序时，判断target是否在 0 ~ mid 之间
            if(nums[0] <= nums[mid]) {
        
                if(nums[0] <= target && target <= nums[mid]) {
        
                    right = mid - 1;
                } else {
        
                    left = mid + 1;
                }
            // 当右半部分为升序时，判断target是否在 mid ~ numsSize - 1 之间
            } else {
        
                if(nums[mid] < target && target <= nums[numsSize - 1]) {
        
                    left = mid + 1;
                } else {
        
                    right = mid - 1;
                }
            }
        }
        return -1;
    }

## 二分代码模板 ##

最后分享一个用Python描述的二分查找算法的代码模板

left, right = 0, len(array) -1
    while left <= right:
        mid = (left + right) / 2
        if array[mid] == target:
            # find the target!!
            break or return result
        elif array[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

[33.]: https://leetcode-cn.com/problems/search-in-rotated-sorted-array/