Show problems as
Classic problem #704EasyArrayBinary Search

Binary Search

Real-world version: Survey Marker Lookup
Tracked in this browser only
Read Binary Search on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstDivide & Conquer · Recursion, animated step by step

A survey crew filed one elevation per marker along a ridge trail, and the office sorted the file from the deepest reading up to the highest. That sorted file reaches you as nums; no two markers share an elevation, and readings below sea level show up as negatives.

An engineer names an elevation target and wants the position of the marker holding it, counting positions from 0. If the file has no marker at that elevation, report -1.

The file can be enormous and the office runs this query constantly, so your routine must halve the range it is still considering on each step rather than reading through the markers one by one.

Examples

Example 1

Input
nums = [-8, -3, 0, 4, 11], target = 11
Output
4

The highest marker in the file carries elevation 11 and sits at position 4.

Example 2

Input
nums = [-8, -3, 0, 4, 11], target = 5
Output
-1

Elevation 5 falls between two filed markers, so no position holds it.

Example 3

Input
nums = [-6000, -25, -6], target = -6
Output
2

Readings under sea level are filed the same way, and this one closes out the file at position 2.

Constraints

  • 1 <= nums.length <= 10^4
  • -10^4 < nums[i], target < 10^4
  • No elevation is filed twice.
  • nums runs from the lowest reading to the highest.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def search(nums: list[int], target: int) -> int:
Java
public int search(int[] nums, int target)

More on the same topics