Java算法题——二分查找法
0 问题描述
给定一个n个元素有序的（升序）整型数组nums和一个目标值target，写一个函数搜索nums中的target，如果目标值存在返回下标，否则返回-1。（定义一个方法，判断某个元素在有序数组中的下角标）
1 代码逻辑
/*** @param a 要查找的有序int数组* @param key 要查找的数值元素* @return 返回找到的元素下标；如果没有找到，返回-1*/
public int binarySearch(int[] a， int key){int low = 0;int high = a.length - 1;if ( key < a[low] || key > a[high] )return -1;while ( low <= high){int mid = ( low + high ) / 2;if( a[mid] < key)low = mid + 1;else if( a[mid] > key )high = mid - 1;elsereturn mid; }return -1;
}
2 小结
二分查找是一种效率较高的查找方法，前提是数据结构必须先排好序，可以在对数时间复杂度内完成查找。
面试考察到了