Binary Search Code 

  int search(const vector<int> &nums, int key) {
    int n = int(nums.size());
    int low = 0; // last index with nums[low] < key
    int high = n-1; // first index with nums[high] >= key

    while (low <= high) {
        int mid = low + (high - low) / 2;

        if (key == nums[mid]) {
            return mid; // found
        }

        if (key < nums[mid])
            high = mid - 1; // search left half
        else
            low = mid + 1; // search right half
    }

    return -1; // not found
}
  
  static int search(int[] nums, int key) {
    int low  = 0;
    int high = nums.length - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;

        if (nums[mid] == key) {
            return mid; // found
        }
        
        if (key < nums[mid]) {
            high = mid - 1; // search left half
        } else {
            low = mid + 1; // search right half
        }
    }
    return -1; // not found
}

 

Putting It All Together 

  int main() {
    vector nums = {2, 4, 9, 12, 12, 12, 43, 78, 85, 89};
    int key = 12;

    BinarySearch binarySearch;
    cout << binarySearch.search(nums, key) << endl;
}
  
  public static void main(String[] args) {
    int[] nums = {2, 4, 9, 12, 12, 12, 43, 78, 85, 89};
    int key = 12;

    System.out.println(search(nums, key));
}

The output should be $3$ or $4$ or $5$:

  4

 

Time Complexity

  • Best case: $O(1)$ - The key happens to be at the very first midpoint examined.
  • Average case: $O(\log n)$ - On average you chop the search space in half until one element is left.
  • Worst case: $O(\log n)$ - You exhaust all halvings (e.g., key not present or at extreme end).

 

Code on GitHub

See the implementation code for Binary Search algorithm.

Last updated 11 May 2025, 02:05 +0500 . history