Binary Search

easy search divide and conquer

Problem

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.

Example 1

Inputnums = [1, 3, 5, 7, 9, 11, 13, 15], target = 13

Output6

nums[6] == 13.

Example 2

Inputnums = [1, 3, 5, 7, 9, 11, 13, 15], target = 4

Output-1

4 is not present in nums.

sorted nums (comma-separated)

target

def binary_search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

function binarySearch(nums, target) {
  let lo = 0, hi = nums.length - 1;
  while (lo <= hi) {
    const mid = (lo + hi) >> 1;
    if (nums[mid] === target) return mid;
    if (nums[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

class Solution {
    public int binarySearch(int[] nums, int target) {
        int lo = 0, hi = nums.length - 1;
        while (lo <= hi) {
            int mid = (lo + hi) >>> 1;
            if (nums[mid] == target) return mid;
            if (nums[mid] < target) lo = mid + 1;
            else hi = mid - 1;
        }
        return -1;
    }
}

int binarySearch(vector<int>& nums, int target) {
    int lo = 0, hi = (int)nums.size() - 1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (nums[mid] == target) return mid;
        if (nums[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

Explanation

Because the array is sorted, we never have to look at numbers one by one. Instead we repeatedly cut the search space in half — that is binary search.

We keep two markers, lo and hi, for the part of the array still worth checking. We look at the middle element between them.

If the middle equals the target, we are done. If the middle is too small, the target must be to the right, so we move lo past the middle. If the middle is too big, the target is to the left, so we move hi before the middle.

Each step throws away half of what is left, so even a huge array is searched in just a handful of steps. If lo passes hi, the target is not there and we return -1.

Example: searching for 13 in [1,3,5,7,9,11,13,15] — check the middle, jump right, check again, and land on 13 in 2–3 steps.

Time: O(log n) Space: O(1)