33. Search in Rotated Sorted Array

https://leetcode.com/problems/search-in-rotated-sorted-array/

C++

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = 0;
        int r = nums.size() - 1;
        while (l <= r) {
            int m = (l + r) / 2;
            if (nums[m] == target) {
                return m;
            }
            bool inLeft = nums[m] > nums[l] && target >= nums[l] && target < nums[m];
            bool notInRight = nums[m] < nums[l] && !(target <= nums[r] && target > nums[m]);
            if (inLeft || notInRight) {
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        return -1;
    }
};

Go

func search(nums []int, target int) int {
    l, r := 0, len(nums)-1
    for l <= r {
        m := (l+r) / 2
        if nums[m] == target {
            return m
        }
        inLeft := nums[m] > nums[l] && target >= nums[l] && target < nums[m]
        notInRight := nums[m] < nums[l] && !(target <= nums[r] && target > nums[m])
        if inLeft || notInRight {
            r = m - 1
        } else {
            l = m + 1
        }
    }
    return -1
}

JavaScript

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
  var l = 0
  var r = nums.length - 1

  while (l <= r) {
    let m = (l + r) / 2 >> 0

    if (nums[m] === target) {
      return m
    }

    let inLeft = nums[m] > nums[l] && target >= nums[l] && target < nums[m]
    let notInRight = nums[m] < nums[l] && !(target <= nums[r] && target > nums[m])

    if (inLeft || notInRight) {
      r = m - 1
    } else {
      l = m + 1
    }
  }

  return -1
}

Python

class Solution(object):

    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        l, r = 0, len(nums) - 1
        while l <= r:
            m = (l + r) // 2
            if nums[m] == target:
                return m
            inLeft = nums[m] > nums[l] and target >= nums[l] and target < nums[m]
            notInRight = nums[m] < nums[l] and not(target <= nums[r] and target > nums[m])
            if inLeft or notInRight:
                r = m - 1
            else:
                l = m + 1
        return -1