Back to Problems

Binary Search

Easy
Binary Search

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

Example 1

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4.

Example 2

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1.

Constraints

  • •1 <= nums.length <= 10^4
  • •-10^4 < nums[i], target < 10^4
  • •All the integers in nums are unique.
  • •nums is sorted in ascending order.
Show Hints (3)
Hint 1: Think about how you can eliminate half of the remaining elements at each step.
Hint 2: If the middle element is greater than target, the target must be in the left half. If smaller, it must be in the right half.
Hint 3: Be careful with the mid calculation to avoid integer overflow: use left + (right - left) / 2 instead of (left + right) / 2.
Loading editor...

Test Results

Click "Run" to execute your code against test cases

AI Tutor

Socratic guidance - I'll ask questions, not give answers

AI Tutor
Hello! I'm your AI tutor, here to guide you through this problem using the Socratic method. I won't give you direct answers, but I'll ask questions and provide hints to help you discover the solution yourself. What's your first instinct when you look at this problem? What approach comes to mind?